Based on my experience with AT&T, if the phone is locked, the provider will only help you unlock it if it is old and off-contract. They don't want you to unlock a new phone because they want you to pay them for service. With T Mobile, YMMV.

I would go the Ebay route, if the person unlocking the phone is a DIY type of person. I have also heard about a guy on the 2nd floor of one of the shopping plazas that cuts SIM cards to fit the micro-SIM slot. He might be able to help. I think he was in the same plaza as the LIME store.