I'm using a Tmobile sim with no problems -- can you explain why that is? I don't think the problem has anything to do with what sim you are using.
It works once you set up the account with any sim. The problem is reflashing and then having to set up the account anew using a t-mobile (and now AT&T too) sim.
It appears this morning that Nokia Messaging re-appeared in the list of providers with a T-Mobile USA sim.
Weird. But it works so not complaining. Welcome back yahho mail!