Maybe you should fix that first. Is the N800 defined as a "trusted device" in your phone?

Yeah, that's what I think to, but I'm not sure what's going on there either and I've not gotten any response on that question in the other thread for help.

I've done everything both Nokia and Sprint say but it still doesn't connect.

GERob

I've had good luck connecting using my LG-VX9800 (the LG-V) on VZW, but it took some hacking on both the N800 and my phone.

On the N800 side, you need to edit /etc/ppp/options to force PAP by disabling CHAP and CHAPv2, by adding the
refuse-chap
refuse-mschap
refuse-mschap-v2
Of course, to do this you need to have root access and a shell; how to do this is well documented at maemo.org; I followed the instructions at http://maemo.org/maemowiki/HowDoiBecomeRoot2.

On the VX-9800, things are a little stickier; you need to set the handset to use only 1xRTT. There's a number of Web pages that describe this, including http://www.howardforums.com/showpost.php?p=6428545. From the idle screen, you'll click "OK" on the inside keypad to bring up the menu, then press "0", followed by the service code "000000". Press 3 for Network select, press 1 for Mode, choose 1x only, and you're done, so press CLR until you're back to the idle screen again. This restricts the entire handset to accessing the network using 1xRTT, so you'll experience slower MMS and disable some features such as V-CAST video. (Fortunately, it's easy to return to the original setting if you want to use the handset with EVDO again using the same menu.)

Once this is done, pair the N800 and the LG. In setting up the connection, the login is your mobile number at vzw3g.com, i.e., 8885554444@vzw3g.com, and the password is just vzw.

As an aside, I think that this should all work for any Verizon phone on which you can disable EVDO and force 1xRTT only mode. I've not tested it with my N800, but I've successfully used DUN with a Motorola V3C and a Motorola V3M on my Mac OS X machine as well, by forcing 1xRTT mode and pairing like you would normally. I'd imagine you could do the same, by first forcing 1xRTT only mode using the handset's test menu as described at http://forum.osnn.net/archive/index.php?t-80153.html. Be careful, though --- you can really mess up the Motorola handsets if you make a mistake using this procedure.

Bear in mind in present that unless you have an unlimited data plan of some sort, say, V-CAST, which is $15.00/month or some such, your data use counts as minutes used against your plan. Moreover, the carrier contract technically forbids tethering, although it's unclear as to whether that's tethering for EVDO access or any data access at all... your mileage may vary.

Cingular + Motorola RAZR V3xx. Cingular 3g data speeds!

Normally I hate verizon, they have crappy phones and lock out alot of features. But I stopped in yesterday and picked up a Moto KRZR k1m for data tethering and some light voice.

All I have to say is WOW verizon's network has extremely fast data. I did some random speed checks with my n800 through out the day yesterday and I was getting anywhere from 465Kbps to 585Kbps. I thought cingular's 3G was fast but it is only about half of verizon's speed.

I am located just south of Boston and the verizon network here is great. Normally I hate verizon and I am a big fan of GSM phones but I can't go back to cingular's slow data.

I picked the KRZR because it supports bluetooth 2.0 and it was pretty cheap only about 50 bucks. The call quality on this phone is pretty bad but like I said I got it mainly for data for both my N800 and Macbook Pro.

How much are you paying a month for tethering?

It isn't really that cheap.

$59.99 tether unlimited data although people do get turned off for about 5 to 10gigs of transfer in one month from what I have read on howardforums

and then the voice plan.

It is rather expensive but compared to just a data card for a laptop its a better deal because you get voice and you can use the data with any bluetooth computer/device.

I am going to LA in a week and a half. I'll test the speed while im there. And Im pretty sure I have layovers in a couple of other cities. I will report later on my findings

Also pairing with the KRZR was really easy I just had to tell the N800 it was a verizon phone and I was online in seconds.

I think I'll stick with my T-mobile plan. It might be a fraction of your speed, but then again, so is the price. I'm paying 20 bucks for edge right now + the voice. Only problem is, I'm thinking about upgrading to the n800 but it doesn't seem to support my T-mobile Dash.

I use the Samsung A900. It forgets the pair every time you turn it off. And battery life sucks. But it also works with the Kyocera KR1 router. You can now get extended batteries from eBay relatively cheap.

Tmobile EDGE with a moto v360 was working fine for some slow web browsing or checking email. However, I was really impressed when I was able to download routes and maps in Maemo Mapper over the bluetooth tether. That doesn't seem to need a really fast connection.