Bluetooth connection to a mobile phone shouldn't be slow, the limitation should be in the phone-to-internet connection, i.e. is it GPRS, EDGE or 3G? (where I live the EDGE nd 3G connections are really bad). If you experience the N800 to phone BT connection as slow then maybe your phone is a BT 1.1 or 1.2 device? The N800 supports BT 2.0 with the EDR extension (http://en.wikipedia.org/wiki/Bluetooth), but even without EDR it should be quite fast.

What my first suggestion was about (see earlier post) is that if you have access to an Ethernet (wired) internet connection then attaching a cheap small wi-fi access point to it would give you N800 wi-fi access to the net, but if you don't have a fixed internet connection like that then this is not an option. Or, if you want mobile internet connection then bluetooth is the way to go. It _should_ be fast enough, as I wrote above.