How do I get my paired Bluetooth device to work properly and show up in Sound Settings as a profile?

I recently paired a brand new Jabra Halo v2 (Supports: HFA, HSP, a2dp) and although the device pairs with Ubuntu 12.04 (same issue in 11.10) just fine it doesn't show up as a audio device profile under Sound Settings.

This appears to be a regression in 12.04. If you visit the launchpad page linked below and both subscribe for updates to the bug and mark it as affecting you, you can help increase its priority.

https://bugs.launchpad.net/ubuntu/+source/pulseaudio/+bug/972063

Try Ubuntu 12.10. I had a lot of problems in 12.04 with the bluetooth. I have a usb bluetooth dongle with Broadcom chipset that works fine - now I can listen music with my MW600 headset and this is A2DP in pulse audio.