if your carrier can't/won't do it, and you need to resort to finding a company on the net to do it for you (with a software unlock), be really careful.
i wasted money twice on 2 different places that seemed to have good reviews, but in the end, they both took the money and instead of doing an unlock, they both just sent emails every 4 or 5 weeks updating the status with reasons why they can't do it yet.
evidently the way that some of these companies work is actually they don't any sort of "work" on the net, they subcontract it out to companies in China and Russia that somehow are able to update the master database of what IMEI are associated with what carrier.
it appears that both of these companies took my money at par value and were waiting for a time when some subcontractor would begin to unlock phones of that model/year/carrier for a certain lower price. and that is how the price they pay is decided. they could have actually contracted with any companies to get it done, but they were waiting for phones of that model/carrier to be offered to be unlocked by some company at a discounted price. also, these companies do it in batches so you might need to wait. (even though both of these companies "promised" it took average 2 weeks, in the email that gets sent to you after you pay they state that they don't even guarantee to be able to unlock it, in which case they dont give you back your money.
its a huge scam.
this was for my iPhone 5 that was registered with and brought through SoftBank in Japan (before the government regulations came into effect that mandated carriers in Japan needed to unlock mobiles).
the unlock never happened.