If anyone would benefit from knowing how to get this working, let me know and I'll post the steps I took to get it working. It's not as fast as EV-DO, but at least you don't need a data plan.

Yeah, I'd like to know how you set that up. Thanks.

You need to install becomeroot, nano(or some text editor), and osso-xterm on the N800. Open X Terminal and type sudo gainroot then enter. Type nano /etc/ppp/options then enter. Remove the # in front of the lines containing +pap and -chap and save the file. You can exit nano and type exit at the console window then enter followed by exit and enter again to close X Terminal.

On the u740, press MENU and have the SETTINGS & TOOLS menu showing. Press # and the User Lock ?????? box should appear. Enter 000000 and press 6. Change the option to CDMA Only Mode and press OK. Press END to return to the home screen.

Now pair the N800 and u740. Goto Tools -> Connection Manager, click the Connection manager menu at the top and select Tools -> Connectivity settings... Click Connections, Verizon Wirless, Edit, Next, and change <MDN>@vzw3g.com to your phone number (ie. 1235551212@vzw3g.com). Click Finish, Done, OK, and exit the Connection manager.

This connection will use your minutes, so I would only recommend it during nights and weekends. The N800 will activate the Bluetooth whenever it wants even if you turn it off. You have to put the N800 in Offline mode by pressing the power button and select it to get it to stop connecting to the u740, then you can turn the Bluetooth off on your phone.

Wow, thanks for making this post! I just got my N800 on Friday and have been driving myself crazy trying to get it to work with my u740. I was also a little nervous following these instructions having never used Linux before but everything worked perfectly!

This site has been really helpful in researching the N800 and figuring out what I can do with it. Thanks!