Also having similar problems with a new Logitech K810 under quantal running on a project sputnik laptop.   bluez-simple-agent doesn't work for me. I either get authentication errors or timeout errors. Can't get it to connect via bluetooth-manager or bluetooth-wizard either. Switched over to blueman, and I am able to get it to connect by selecting "Proceed without pairing", but that isn't persistent, so I have to that every time I connect right now.

Here is the debug output from bluetoothd when attempting to pair properly  via passkey and failing:

start pairing:

bluetoothd[4762]: src/adapter.c:adapter_create_device() 00:1F:20:4D:96:8B
bluetoothd[4762]: src/device.c:device_create() Creating device /org/bluez/4762/hci0/dev_00_1F_20_4D_96_8B
bluetoothd[4762]: src/device.c:btd_device_ref() 0x7ffceb6b2fa0: ref=1
bluetoothd[4762]: src/device.c:device_set_temporary() temporary 1
bluetoothd[4762]: plugins/mgmtops.c:mgmt_create_bonding() hci0 bdaddr 00:1F:20:4D:96:8B io_cap 0x01
bluetoothd[4762]: src/device.c:bonding_request_new() Requesting bonding for 00:1F:20:4D:96:8B
bluetoothd[4762]: src/device.c:bonding_request_new() Temporary agent registered for 00:1F:20:4D:96:8B at :1.125:/
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() cond 1
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() Received 39 bytes from management socket
bluetoothd[4762]: plugins/mgmtops.c:mgmt_device_connected() hci0 device 00:1F:20:4D:96:8B connected eir_len 20
bluetoothd[4762]: src/adapter.c:adapter_get_device() 00:1F:20:4D:96:8B

entered passkey:

bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() cond 1
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() Received 14 bytes from management socket
bluetoothd[4762]: plugins/mgmtops.c:mgmt_auth_failed() hci0 auth failed status 5
bluetoothd[4762]: src/device.c:device_bonding_complete() bonding 0x7ffceb6b2d30 status 0x05
bluetoothd[4762]: src/device.c:device_cancel_bonding() Canceling bonding request for 00:1F:20:4D:96:8B
bluetoothd[4762]: plugins/mgmtops.c:mgmt_cancel_bonding() hci0 bdaddr 00:1F:20:4D:96:8B
bluetoothd[4762]: src/agent.c:agent_release() Releasing agent :1.125, /
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() cond 1
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() Received 16 bytes from management socket
bluetoothd[4762]: plugins/mgmtops.c:mgmt_cmd_complete() 
bluetoothd[4762]: plugins/mgmtops.c:pair_device_complete() hci0 00:1F:20:4D:96:8B pairing complete status 5
bluetoothd[4762]: src/device.c:device_bonding_complete() bonding (nil) status 0x05
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() cond 1
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() Received 9 bytes from management socket
bluetoothd[4762]: hci0: Cancel Pair Device (0x001a) failed: Invalid Parameters (0x0d)
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() cond 1
bluetoothd[4762]: plugins/mgmtops.c:mgmt_event() Received 13 bytes from management socket
bluetoothd[4762]: plugins/mgmtops.c:mgmt_device_disconnected() hci0 device 00:1F:20:4D:96:8B disconnected
bluetoothd[4762]: src/event.c:btd_event_disconn_complete() 
bluetoothd[4762]: src/adapter.c:adapter_remove_connection() 
bluetoothd[4762]: src/adapter.c:adapter_remove_connection() Removing temporary device /org/bluez/4762/hci0/dev_00_1F_20_4D_96_8B
bluetoothd[4762]: src/device.c:device_remove() Removing device /org/bluez/4762/hci0/dev_00_1F_20_4D_96_8B
bluetoothd[4762]: src/device.c:btd_device_unref() 0x7ffceb6b2fa0: ref=0
bluetoothd[4762]: src/device.c:device_free() 0x7ffceb6b2fa0