first off, have you checked that your phone is actually network locked?
If so and you purchased it from Virgin Mobile. Call the team on 789 or 0345 6000 789 from any other phone. Give them the phone details and your account information, they should be able to supply an unlock code (I think the charge is around £15).
If you want to say thanks > click 'Kudos'. Answered your question? > click 'Mark as Helpful Answer' also.
Virgin iPhones are locked to Virgin when they're activated and you have to phone up to get it unlocked. I thought that it would lock to the next network you register it to but that might not be the case (although I can't find a definitive answer on that).
Massage an ego, click the kudos button. If someone answers your question, mark it as helpful. Be nice, eat all your vegetables and keep your room tidy.