I had this same problem today.
After speaking with TMO to find out that I had the right services on my account and there was no magic Tethering plan like cingular, I uninstalled everything.
Rebooted.
Follwed the usual directions I found in the forums, but I did like CAGirl and left the username and password blank.
I used the initialization string, +cgdcont=1,"IP","wap.voicestream.com"
Everything is now working.