I believe when I had this problem, I needed to change the name of the access point from something like "internet2.voicestream.com" to "wap.voicestream.com". Then I had no problem.

You might need some proxy settings as well. Check out these settings (from another recent post):

Access point name: wap.voicestream.com
Dial-up number: *99#
User name: leave blank
Password: leave blank

Click the [advanced] and check "Use Proxy"
HTTP Proxy: 216.155.165.50
Port: 8080
HTTPS Proxy: 216.155.165.50
Port: 8080

Good luck.

-F