Stream setup failed for Bluetooth headphones

Problem

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

Solution

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