Just had this problem after coming from using the phone overseas and no signal whatsoever on the phone despite numerous restarts, SIM cleaning, and chats with T mobile. After verifying the APN was correct I went to Settings-->About Phone-->Status-->SIM Status and checked to see if the SIM was connected(it showed my phone number, but was disconnected). So from here went to Settings-->Mobile Networks-->Network Operators and let the phone find carriers automatically. Mine showed T-mobile(with a little SIM icon to the right of it), Verizon, and ATT. I clicked on T-Mobile and it registered and is now working.
Probably saved me $15 at the T-Mobile store. Hope this helps even just one of you.