If you’re using GNOME, you probably have gnome-bluetooth installed, but unfortunately it doesn’t support A2DP, so a stereo headset won’t work properly. Installing Blueman can fix this.
On Ubuntu, to automatically route audio to connected headphones, you’ll also need PulseAudio installed. This tool will also help you configure audio for different applications.
First, remove the old packages responsible for Bluetooth. For gnome-bluetooth, that’s libgnome-bluetooth11.
apt-get remove libgnome-bluetooth11
apt-get autoremove
You can reboot now. After that, start installing the new packages.
apt-get install pulseaudio-module-bluetooth
apt-get install "pulseaudio-*"
apt-get install bluez-utils
apt-get purge blueman
add-apt-repository ppa:cschramm/blueman
apt-get update && sudo apt-get install blueman pavucontrol pulseaudio-module-bluetooth -y
apt-get install pulseaudio-module-bluetooth
pactl load-module module-bluetooth-discover
Reboot once more. If everything went well, you should see a Bluetooth icon in the system tray. Click it to add a new device and pair your new headphones. If the headset asks for a PIN, try 0000 or 11111. If that doesn’t work, check the user manual that came with the headphones.