I just bought the Nokia N800 and so far loving it. It took me about half hour to figure out how to set up Bluetooth DUN tethering of my Sprint PPC-6700 Windows mobile 5 device with Nokia N800. It works great. Here is a summary of the steps (I am writing from my memory so some may be a little off) :

• MAKE SURE THAT YOU HAVE THE PROPER UNLIMITED DATA PLAN TO AVOID DATA USAGE CHARGES.
  
  
• On the Sprint PPC-6700, go to Start-->Settings-->Connections and then click on Bluetooth. Check both the items that say "Turn on Bluetooth" and "Make this device discoverable to other devices".
  
  
• On Nokia N800, go to Tools-->Control panel and double tap the item that says Bluetooth. Select the check box to turn it on and make it visible and click OK. Then tap the item in the control panel called "Phone" twice and then tap "New" button under the Selected Phone window. N800 will now search for your PPC-6700 bluetooth connection and you will see it in the list of phones. Select it and click OK.
  
  
• You will now see a screen on your N800 to "Pair with device" with a 4-digit numeric passcode. You can change it if you want. Write this passcode down. If you see your PPC-6700, you will see a prompt from N800 asking permission to connect. Allow the connection and enter the passcode on PPC-6700 when requested.
  
  
• Next, go to your PPC-6700 and select Start-->Programs and click on "Wireless Modem". From the "Connection Type" dropdown, select "Bluetooth" and click on the "Start" button. This will activate the Bluetooth DUN feature of PPC-6700.
  
  
• Now go to N800 Control Panel and double tap on "Connectivity". It will open a small window and you click on the "Connections" button in the middle (bottom). Click on "New" to start the Connection setup wizard and tap Next. Give a connection name of your choice such as "my PPC6700" and select the "Data call" radio button. Click Next. From the cellular network drop down, select CDMA. Click OK. In the Dial-up number, enter #777. Leave the Username and password fields blank. Click next and then click Finish.
  
  
• You are done. Now try to get online and select the connection you just created. It should work fine (the speed is not as fast as Wifi but not too bad either).
  
  
• After you are done, make sure to go back to PPC-6700 WModem screen and click on the "Stop" button to turn off the phone as a modem connection.

That's it!! Enjoy!!

You might get charged for data doing it that way. Better idea. Download & installl UsbModem on the PPC6700.

Thanks jhford. Could you please elaborate more? Where can I download and install the UsbModem that you mentioned?

The way I connected (using the instructions in my original post), I used the default Wireless modem software that comes with the phone. I the past I had used the exact same software to connect my Windows XP laptop to the phone using the USB cable and the XP drivers that came on the CD. This time, I connected using the Bluetooth (instead of USB, not sure if N800 can do USB)with N800 but the rest of the process was the same. I have never been charged extra data usage on top of my unlimited vision data plan when using the laptop (I use occasionally, maybe half an hour in a month, if that).