PROBLEM SOLVED!!! I was finally able to get my Nokia N800 to use my Verizon Motorola Q to connect to the internet via Bluetooth DUN!!!

a. I updated my Motorola Q to the latest firmware (MOL3).
b. Installed PdaNet 1.80.
c. Since Bluetooth was already on, I simple enabled BT DUN in PdaNet. I think this made the PdaIcon have a little, red BT icon on it.
d. Restarted my Moto Q.
e. Made sure my desktop could connect to the web via PdaNet and the Moto Q (i was getting error 691 before I reset the phone)
f. Deleted the old pairing on the N800
g. Paired the N800 with the Moto Q
h. I canceled the "cellular operator" wizard
i. I created a new gprs connection.
j. I left the access point name as "internet", dialup=#777, username and pass are blank, clicked finished.
k. I connected with no problem.

I guess the firmware was the fix. Thanks for the help.