My bluetooth mouse (Dell BT Mouse) was working fine in Ubuntu after installing the OS. I just followed the gui prompts to connect it.
Then, after some time (right around the time I paired the same mouse with the windows OS installed on the same machine), the BT mouse stopped working. I tried again and again to pair it and it failed.
After trying somebody else's guide using bluez-util, simply went to System\Preferences\Bluetooth and found the mouse under "Known Devices". After removing it, I was able to easily use the bluetooth GUI (that appears on the top panel in Gnome) to add my mouse again and it works perfectly.