Ubuntu has a problem pairing bluetooth keyboards. I found the solution at http://devasive.blogspot.com/2012/11/ubuntu-1204-persistent-bluetooth-pairing.html

For Ubuntu 12.10, the instructions are a tiny bit different due to a bug in bluez.
1. Make sure your root (sudo -s in all).
2. apt-get install bluez-hcidump
3. Run “hcitool scan” to get the MAC Address.
4. Run “hcidump -at” to watch for the PIN needed to pair.
5. Run “bluez-simple-agent hci0 {MAC}” in another window and watch for the PIN in the window with hcidump.
6. Enter the PIN on the keyboard and hit return.
7. Run “bluez-test-device trusted {MAC} yes” to addthe keyboard as a trusted device.
8. Run “bluez-test-input connect {MAC}” to test the keyboard.
9. Reboot.

Hope this helps someone. I used the above to pair the Logitech k811, but should also work for the k810 and possibly other keyboards.