Changing carriers and sims - how do I know if the new network will work?
Good choice (T-Mobile). If your phone is unlocked you should be able to use your device with most carriers, especially the ones who activate service with a SIM card. 

It's most likely because it's not registered yet, I wouldn't see any reason otherwise. 

Update

I'll agree with Eldrerathis here. It's possible that the device cannot connect to the network correctly.