I had this exact same problem, and could not get it resolved through Nokia’s tutorials, or by using any of T-Mobile’s OTA updates. I now have stumbled across a solution, purely by trial and error, and would like to share what finally worked for me. The following assumes that you have already successfully paired your N800 with your mobile phone.

In the N800’s Connectivity Control Panel, click Connections, then New [or edit your existing connection to match], name the connection “T-Mobile Internet” , and set the connection type as “Data Call”. Click next. Set the dial-up number as “*99#”, leaving all other fields on this screen blank. Click next. On the next screen click advanced. On the advanced screen click the Other tab, and in the Supplementary AT Commands field, enter “at+cgdcont=1,"IP","internet3.voicestream.com”. Click OK. Click Finish.
Back at the top menu bar, click the globe icon, then select connection, and choose the connection you have just created. At this point the globe icon will begin blinking a phone icon right in front of it, and after a few moments you should see “Connected to T-Mobile Internet” in a pop-up window.

Hope this helps!