For Xmas I got an N800 and a Samsung M500 + Sprint SERO (unlimited EVDO).

I flashed the N800 to OS2008, installed vpnc-gui and rdesktop and everything seems to work good connecting to work with my wlan (DD-WRT). Need to use the onscreen keyboard under WindowsXP on the remote end to type tho - use Start > Programs > Accessories > Accessibility > On-Screen Keyboard to activate.

However, it doesn't work with bluetooth DUN to my M500. I did a quick debug (gainroot+xterm+modded vpc-script) and it looks like the start script creates route commands that busybox cant understand. I wrote a quick email to the developer and received a prompt reply verifying the issue, so there might be a fix in the next version!

Looks like Bluetooth pairing on the M500 is pretty broken. Its easy to set up as a phone on the N800 and to use for Sprint EVDO access using the default connection profile but you have to use a code to pair each time as the M500 usually hangs if you try to set it up the N800 as a trusted device (either from the phone or the N800).

Now some people might find this ok - a trivial amount of hassle for $30/mo EVDO access, but it drives me crazy! Totally unacceptable.

Update: I had to go through it all again because I reflashed to the lastest OS2008. My previous instructions didn't work - I tried many times.

I noticed however that if I attempted to pair the M500 with the N800 Connection manager and hit Cancel when it was pairing sometimes the M500 paired successfully if I let the communication go on long enough. I tried it the other way round, attempting to pair the N800 from the M500 and hitting Cancel on the M500 - sure enough the N800 thought it had paired successfully!

Unfortunately whichever device I hit cancel on failed to pair Doh!

Finally I was getting a beer from the fridge when I had an epiphany - I need the bluetooth conversation to be interrupted after enough information has been passed between the devices but before the communication completes and the M500 hangs.

This works every time:

1) on M500: Options > Settings > Bluetooth > Add New > Wait For Connection, then place M500 far away in corner of room (I buried it under bags of change)

2) on N800: Control Panel > Bluetooth > Devices > New, find the M500 and attempt to pair

3) When prompted type in code on N800 and click ok (button will go gray)

4) Count to 3 (quickly - maybe 2secs?) and throw N800 in Fridge and close the door.

5) Go check M500 has added N800 as trusted device. Wait a minute and retrieve N800 from fridge - it too will have successfully paired.

Ta da! No nasty hard resets or anything.

If M500 hangs during pairing try moving it further away and count quicker before placing N800 in Fridge - you'll get the hang of it

Update: Samsung M500 + N800 + Sprint SERO is great - pairing was a hassle but its a good combination and has been painless since it was set up - just need to be near a refrigerator next time there is a firmware update

I have an N810 and am having essentially the same problem you had. Any attempt to pair the N810 with M500 results in it locking up. Using the refrigerator procedure you describe, I can actually get them to pair (crazy!). However, if I use this procedure, the N810 doesn't seem to recognize the M500 as a phone. It does not prompt me to set up and internet connection, and "Sprint" no longer appears in the Connection Manager. Did you have a similar problem? How did you get around it?

Update: After trying like 10 more times, I apparently timed it just right such that both ends got enough information to pair successfully, but not so much that the M500 locked up.

Before that, though, I found the misconfigured bit in the N810. gconftool -R /system/bluetooth/ADDRESS/services had a bare list. When the N810 paired properly, the list was:

services = [telephony,object transfer,capturing,networking,DUN,OPP,00001112-0000-1000-8000-00805f9b34fb,HFP-AG,FTP,0000110a-0000-1000-8000-00805f9b34fb,0000110c-0000-1000-8000-00805f9b34fb]

Probably DUN is the only one that matters in that list. Some other relevant keys are:

dun_gsm = false
dun_umts = false
dun_cdma = true

So, with some gconftool magic, I bet I could have overridden the faulty keys on the N810 to get working internet without wearing out the door on my fridge