I have paired my linux desktop and the n800, but the n800 says

Searching for 00:11:22:33:44:55 ...
Error org.bluez.network.Error.NotSupported: The service is not supported by the remote device
Setting up connection to 00:11:22:33:44:55 failed

where 1...5 is the mac address of the desktop machine. I have tried enablind and disabled authentication and encrytion on the desktop, with short and long PIN.

--edit--

BTW, my current attempt at a class is 0x960100, the nokia gets this using sdp-query...

# sdp-query 00:11:22:33:44:55
r|OPP|10|0|OBEX Object Push
l|0x1116|15|0|Network Access Point
r|0x1102|1|0|LAN Access Point