Comment 38 for bug 630001

I managed to make this work, by updating bluez to a newer version found in Brian Rogers repository.

add-apt-repository ppa:brian-rogers/ppa
apt-get update
apt-get install bluez

After this it paired at first time, however it looked like there ware multiple keypresses. After a reboot, it is working flawlessly.