Well, after playing around with it for a while, I finally got it to work. I can now connect via BT DUN through my Verizon Treo 700w. I can even get it to show up in my "Select connection" screen. Here are the steps I would recommend based on my trial/error:

1 - If you have any phones setup to be paired with the N800, delete those from the BT Devices list (Tools -> Control Panel -> Bluetooth -> Devices).

2 - If you have gone through the "Mobile operator setup wizard", delete that connection as well (Tools -> Control Panel -> Connectivity-> Connections).

3 - Now we'll setup the BT connection to the phone. Make sure your phone has BT turned on and is in discoverable mode. On the N800, go to Tools -> Connection Manager -> Tools (in the Connection Manager drop-down) -> Phone... In the Phone dialog menu, choose new. Th N800 will the search for your phone. Highlight it and hot OK. You'llthen get the "Pair with a device" dialog screen. It'll display a pass code that you can use (or change to whatever 4 digit code you want). Hit OK and your phone should then prompt you to pair with the N800 and ask for the pass code. Don't worry about the next screen on your phone which may not show any services for the N800 (on the Treo 700w, Verizon disables BT DUN, so I use pdanet as a workaround. BT DUN works, but the BT data service doesn't show up in the N800 pairing profile since pdanet is essentially a hack).

4 - After successful pairing, the N800 immediately gives you a new dialog window called "Operator setup". If you should cancel out of this accidentally, you can get back to it (Tools -> Connection Manager -> Tools (in the Connection Manager drop-down) -> Mobile operator setup wizard...). This is what takes the BT pairing connection and sets it up for use on the N800 essentially as a wireless modem. Now, this next step seems odd, but it works. Step 2/4 in that dialog box asks you to choose a country - Verizon folks choose USA of course. However in step 3/4, you are presented with a list of carriers, all of which appear to be GSM carriers. There is no selection for CDMA.

It is important to actually choose one of the choices from the drop-down list even though Verizon isn't listed. For reasons made clear in the BUG area below, you have to choose the wrong carrier. Hopefully, Nokia will fix this.

All choosing one of these does is fill in pre-defined connection detail fields for that carrier. These details can be changed later. Because pdanet is handling the dialing responsibilities and username/password duties on my Treo 700w, it doesn't matter what connection settings are on the N800 (pdanet appears to ignore these details and use its own). Going through the Mobile operator setup is important though in order to let the N800 know that there is a BT DUN connection available.

I chose "T-Mobile Internet". After completing this, "T-Mobile Internet" appears as a selection in the "Select connection" window. You can change the name of that connection to whatever you want by going to Tools -> Control Panel -> Connectivity-> Connections. Select the connection and hit Edit. For Verizon users with pdanet, you're done. You can now use this connection by choosing it from the "Select connection" window.

This is where we need someone to test on a phone other than one using pdanet. Pdanet is filling in the gaps here and my recommendations on connection settings below should be tested on a Verizon phone without pdanet to see if this workaround can be used for all Verizon phones.

For non-pdanet Verizon users, the connections edit dialog box is also where the connection details can be changed that may solve their problem. So, the first screen is the connection name and type. Leave "Packet data" selected. The next screen is where some testing is required.

- I'd say try leaving "Access point name" blank. This isn't an available field when you setup Verizon as the mobile operator (more on that below), so try leaving it blank.
- "Dial-up number" for Verizon is #777
- "User name" is listed as <MDN>@vzw3g.com in the pre-defined Verizon mobile operator settings (again, more on that below) so try that. you could also try replacing <MDN> with your mobile number.
- "Password" is vzw

Bug Bug Bug

There appears to be a bug in the "Mobile operator setup" process for Verizon (and perhaps all listed CDMA carriers). If you do step 1 and 2 above and then instead go to "Mobile operator setup" (essentially reversing the order of steps 3 and 4 above), you are given a dialog box with a choice of carrier type (GSM or CDMA). If you choose CDMA, you can select Verizon. After that, you then get the phone setup dialog asking you to pair the phone.

Seems like this should be the way to setup for Verizon right? Only one problem, that new connection for Verizon will never show up in the "Select connections" window. I've tried it over and over, deleting everything and trying again. With the "Phone connection" selected in the "Connect Automaticaly" field (Tools -> Control Panel -> Connectivity), the N800 will attempt to use this created Verizon connection. You can see it trying to make a connection if you have the Connection Manager open, but it won't ever connect. This pretty clearly seems like a bug.

Hope this helps and please post back about if you do any testing with non-pdanet phones on Verizon.

Jeff