I've had the same pairing-after-a-restore problem that other people here have described, specifically the immediate "pairing failed" error you get trying to pair a BT keyboard. It's fixable without downgrading or reflashing, but you've got to get root access and be comfortable using vi (or any other in-terminal text editor) to do it.

So: install the X terminal, ssh client and server. It will ask you to change your password to something non-default, so do that.

ssh root@localhost, and login.

key in "cd /var/lib/blue" and then hit tab twice, tab-completion gets you into /var/lib/bluetooth/-your bt mac address-/

then do an ls, and that will show you a list of your bluetooth configuration files. so, flip over your keyboard and make a note of its mac address.

Then, open each of the files in that directory in turn, and delete any line that references that mac address and, if they're there, any empty blank lines at the beginning of the file.

Log out, power down and restart the n800. Now the pairing process should work as advertised.

Good luck.