Thought your phone may need a SIM unlock code but probably not since there is no prompt.
Just to confirm how you checked if the phone is unlocked --- When you go into Settings, Security and SIM Manager (way to access may be different based on your ROM) does the phone prompt you for a code or does it respond that it is already unlocked?
Only other thing I can think of is to try a friend's SIM from AT&T or another carrier to see if it works so you can at least be sure that the GSM radio of the phone works.
I have not tried a T-Mobile SIM but I did try an AT&T SIM when I unlocked my phone and it was recognized without any problem. Hope it is not possible for T-Mobile to lock the SIM card to a particular phone.