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.