I couldn't get it to work with my work desktop using an external bluetooth dongle either (set as desktop or laptop) even though it supports PAN. The N800 doesn't recognize my work desktop as a phone therefore bluetooth-pan doesn't see it.

However the N800 recognizes my Dell laptop with built-in Dell BT dongle as a phone and bluetooth-PAN works.

You can also use WiFi network card and set up an ad-hoc network to share connection. It's also faster than BT.

Remember to set the default gateway of your BT network as 192.168.0.x.