I've found that using Bluetooth devices with Ubuntu is really convenient. Pairing, connecting and customizing other settings can be done right from the top panel by clicking on the Bluetooth icon.
However, sometimes Ubuntu silently refuses to connect to the Bluetooth device. Or it refuses to turn on. Or it does not list any of the paired devices. In my experience these problems typically happen after my notebook computer has been resumed from a sleep or suspend. This happens even though the device has been paired. And it does not connect even if Bluetooth is turned off and then on from the panel.
I've found that I can get Bluetooth working again by restarting the Bluetooth service:
$ sudo /etc/init.d/bluetooth restart
Tried with: Ubuntu 12.04 LTS