Seems to be an issue with this mouse since the version 9.04: even though gnome bluetooth interface can scan the device, the paring is not done.
Solution: install backward compat packages:

sudo apt-get install bluez-compat

Then put your mouse in paring mode and:

sudo hidd -s