I am having the same issue except with my Apple Wireless Keyboard. The keyboard worked exceptionally well in OS2007, paired with minor issues in the beta of OS2008 and won't give me the chance to enter the passkey in the latest OS2008.

Is anyone else having the issue where the N800 sees the keyboard connects, but then does not provide time to enter a passkey before saying the pairing failed?

Any help?