Use a GUI para iniciar o processo de configuração, como normal. A senha impressa no bluetooth gui está errada, então você precisa instalar algumas ferramentas.
sudo apt-get install bluez-hcidump
sudo apt-get install bluez-utils blueman
Em um tipo de console
sudo hcidump -at | grep -A 1 "User Passkey Notification"
que exibirá a senha correta.
2013-09-25 14:35:40.653393
HCI Event: User Passkey Notification (0x3b) plen 10
bdaddr XX:XX:XX:XX:XX:XX passkey 66235
Digite a chave de acesso no teclado Bluetooth e pressione Enter.
Reinicie e você poderá ver que o bluetooth gui ainda registra seu novo teclado.