On my Dell Precision M4500 with embedded Bluetooth device I've used for 6 month a Logitech M555b Bluetooth Mouse on Ubuntu 10.04 with no problem.
After the latest update (Automatic Update) of Ubuntu, my mouse stopped pairing with my pc.
I deleted the device from the Bluetooth Preferences device list and clicked again "Set Up New Device" button, but in the device search the mouse appear and disappear, or if I select the mouse from the list and I can click the "Forward" button it gives me an error like that one:
Some times a popup comes out, and say a thing like:
Grant access to '0000 ... other number loong number'
Device "Logitech Bluetooth Mouse M555b" (00:??:?? other numbers separated with ":")
wants access to the service
'0000... other number loong number similar to the first one...'.
There is also a Bug Report about this issue:
https://bugs.launchpad.net/ubuntu/+source/bluez/+bug/774854