It would be pretty pointless to call T-Mobile. They are happy to help if your unlocked iPhone is up and running and you are trying to use features, but they won't help getting your iphone actually set up.
I may be wrong, but it kind of sounds like a old sim card. Might try getting a new one and giving it a try.
One good test to see if that is true is borrowing someone else's sim, drop it in the phone and see if their's will work. If it does, you just need a new sim, if not, probably need to restore and start over.
One other thing, did you turn the 3G function to "off" before inserting your sim? Apparently that causes problems also.