After following this thread, I too have successfully paired my iGo Sierra with my OS2008 N800 (THANK YOU!!!). In fact, to simplify the process:

1) Install osso-xterm, nano (or vi) and becomeroot if not done already
2) Open up Xterm, type "sudo gainroot" to become root
3) Type "cd /var/lib/bluetooth/*" to access your device's BT directory
4) Just clear out all the files EXCEPT for config. To do this, open each in nano or vi and clear the lines within, then save the files. Each line should start with a MAC address. Note: *Don't delete the files!*
5) Reboot the N800 and try pairing normally - i.e. turn on Bluetooth, search for devices, hit the button on your keyboard to activate it, and pair it by holding Fn and typing the passcode, then mashing Fn+OK a few times. Now the N800 should actually wait for you to get the code right instead of saying "Pairing Failed" immediately.

This removes the future problems of any other devices previously paired with the N800 - this way when I go to link to my friend's phone (that I had paired with back in OS2007) I won't run into this "Pairing Failed" problem again.

<EDIT> I'd only clear out the files if this is the first BT device you're trying to pair. If you've already successfully paireed other devices, I'd follow the advice about finding your keyboard's MAC address as explained on above posts.