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 ins...