I remember how frustrating this was for me, too! In my case, the culprit seemed to be that I had gotten the keyboard paired, THEN upgraded to 2008OS, THEN restored. Then I had precisely the problem you did.

To fix it, I did roughly this:

1. install the xterm app
2. install gainroot
3. install nano (a non-graphic editor)
4. went to the terminal, then became root, then edited the files in
/var/lib/bluetooth/00... (where the 00... stands for the Mac address of the N800)
to remove all the lines that referred to the Mac address of the keyboard.
5. try to pair again. After all the above, trying to pair worked correctly (as in, "it actually gave me time to try to type in the pairing code").

If you DIDN'T have it working before, I don't know as this will help. If it looks like this might help you, but you haven't a clue how to do step 4, just let me know. It was tedious, but not impossible.