First step. In the control panel open Bluetooth > check on > then check visible. It will now show an icon on the status bar.

In my experience once they are paired as Briand said they stay paired, but perhaps when you try to re-pair it causes problems?

To re-pair be sure that you again press the Control key and the two FN keys at the same time till the green sync light flashes on the keyboard, start the pairing from the n800 then enter the new code from the nokia and proceed

Good luck