I have that exact setup working. I had to add a new data communication profile to the phone, and configure the N800 to use the correct connection ID (CID).

On the phone:

Menu > Settings (#) > Connectivity > Data communication > Data accounts > New account

APN: internet
Username: web
Password: web or wap (can't remember which, this says which, though)
Login request: off
Allow calls: automatic
IP address: blank
DNS address: blank
Authentication: none, PAP and CHAP
Data compression: off
Header compression: off

Then go to More > Account info and make a note of the external ID.

On the N800:

Not got one to hand, however go to the connection advanced settings and put the external ID digit in the connection string. Should be fairly obvious within the AT-string.

HTH,

Andrew