I have a Bluetooth adapter and a Bluetooth headset which worked fine on an Ubuntu system. I now plug them into another XUbuntu system. It uses Blueman, a GTK-based GUI tool for managing Bluetooth devices. I can discover the headset and connect to it. However, it does not appear as an Output Device in Sound Settings. So, I cannot use it as Audio Sink for any playback.
On diagnosing the problem in Blueman, it gives this error for this headset:
Connection Failed: Stream setup failed
It turned out that this computer first had Ubuntu and XUbuntu was installed on top of it. Ubuntu uses a GNOME Bluetooth manager and XUbuntu uses Blueman.
To solve this problem, I uninstalled Blueman:
$ sudo apt-get purge blueman
After restarting, I used only the GNOME Bluetooth manager and was able to connect the headset. It appeared as Output Device in Sound Settings and I was able to use it to listen to audio.
Tried with: Creative WP-300 headphones, ioGear Bluetooth adapter GBU521 and Ubuntu 14.04