I resolved my problem. After many tries at pairing and failing I resorted to desperate measures and pulled the battery from the N800, waited a couple of minutes and then put the battery back in. After this I could immediately pair with the keyboard with no problems.

Gary