Comment 9 for bug 1035431

Hi there..
I had the same issue as you but I solved it while playing around on LinuxMint (with a logitech K810). The issue is that once you type in "sudo bluez-simple-agent hci0 XX:XX:XX:XX:XX:XX" the computer waits for a passkey, which never arrives, because you don't know what it is. Using the "bluez hcidump" tool (install if required), you can see what the passkey is and type it into the K810 before the connection times out.
Below is copied & pasted from the link you mentioned, plus what I did to get my K810 to work:

In a new terminal type:
"hcitool scan" and copy mac address XX:XX:XX:XX:XX:XX

Now in another terminal type:
"sudo hcidump -at"

You should get something like (followed by a blinking cursor):
HCI sniffer - Bluetooth packet analyzer ver 2.4
device: hci0 snap_len: 1028 filter: 0xffffffffffffffff

Switch back to your original terminal and type:
"sudo bluez-simple-agent hci0 XX:XX:XX:XX:XX:XX"

Now in the hcidump terminal you will see a few things scroll past until you get something that looks like:
2013-02-07 15:35:40.653393 > HCI Event: User Passkey Notification (0x3b) plen 10
    bdaddr XX:XX:XX:XX:XX:XX passkey 66235

Type the 'passkey' in to the keyboard on the K810 and press ENTER
On success you should get "Release" and "New device (/org/bluez/..."

Now set device as trusted:
"sudo bluez-test-device trusted XX:XX:XX:XX:XX:XX yes"

You might have a connection now, but still need to:
"sudo bluez-test-input connect XX:XX:XX:XX:XX:XX"

Now reboot and hope for the best!