This is adapted from StackExchange, from the answer of Yury Kirienko.

1. Install Blueman: sudo apt-get install blueman
2. Download bluez-5.53 (or later) from http://www.bluez.org/release-of-bluez-5-54-and-5-53/
3. unpack: tar -xf bluez-5.52.tar.xz
4. Do cd bluez-5.52
5. Try in the terminal: ./configure
6. The configuration fail for me. If it fails for you try installing

   sudo apt install libdbus-1-dev libudev-dev libical-dev libreadline-dev

7. Try again: ./configure
8. Compile: make
9. Install: sudo make install
10. Install
11. Restart your computer.
12. Open blue manager
13. Pair the headphones as audosink (to pair, unpair headphones first).
14. Select the Bluetooth audio source in Ubuntu
15. This should work.

EDIT:

If PulseAudio fails when changing the profile to A2DP with bluez 4.1+ and PulseAudio 3.0+, you can try disabling the Socket interface from /etc/bluetooth/main.conf by removing the line Enable=Socket and adding line Disable=Socket.” And then restart using

sudo systemctl restart bluetooth