I didn't have many problems connecting with Ubuntu 12.04 64 Bit.
I clicked on the Bluetooth icon in the corner (The little 'B").
Then I clicked on "Set Up New Device".
That opened the Bluetooth New Device Setup. Press Continue. It will scan for devices.
Automatic PIN detection did not work, but I clicked on "PIN options..." and selected '0000' (most headsets, etc).
Then I clicked Continue and it connected.
To get sound to output, I cliked again on the Blutooth 'B' and under "Devices" I hovered on HiddenRadio, and went to "Sound Settings".
On the settings page, Clikc on Hidden Radio, and sound will come from the Hidden Radio.