Next
Check if you have the following packages installed on Linux:
bluez-btsco
pulseaudio-module-bluetooth
libsbc1
Install any package that you don’t have on the list above. If you do do end up having to install any of them, you’ll need to restart the bluetooth service or reboot your system.
This actually helped me a lot. My devices were pairing and connecting but not playing audio. I’m not a Bluetooth expert and I was stuck. Thanks, guys!
Already tried those.
This is just to mention I strongly appreciated marfig’s answer, which solved the issue I had on two Tuxedo laptops, both with U-Mate preloaded by Tuxedo 
Thanks again to marfig and u-mate.community!
Hervé
I would like to add to this Bluetooth/ Headphone discussion. I was having all of the above problems “Bluetooth headphone won’t work”
Running Ubuntu Mate 16.04, Sony Bluetooth Headphone MDR-ZX22OBT, and at first a cheap generic bluetooth adapter and now the IOGEAR 4 adapter.
Now thanks to marfig and his detailed instructions plus trial and error, i’m now on bluetooth headphones Cable free, you beauty!!
So I checked or installed these:- bluez-btsco, pulseaudio-module-bluetooth, libsbc1
Then removed the already entry for the headphone from the Bluetooth program.
Restarted the PC with the IOGEAR adapter installed.
Started the “Setup New Device” in Bluetooth Manager ( is that called Blueman ? )
I now had my headphones showing in Sound Preferences (PulseAudio Volume Contol) and the speaker test was working but I still had no audio in the headphones
I had to change the “Playback” settings in “Volume Control” from the Built-in Audio Analogue Stereo, to my headset. This shows when you put the curser on that box with the Audio program playing a tune
After selecting my headphones the audio came on straight away.
Thanks again, marfig
Image of “Volume Control" Playback setting
Glad you got your Bluetooth working.
Wish I could say the same. I get "failed to pair device."
andyk_~/Downloads$ lsusb
Bus 005 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub
Bus 002 Device 005: ID 04f9:0045 Brother Industries, Ltd
Bus 002 Device 004: ID 04a9:1760 Canon, Inc.
Bus 002 Device 003: ID 045e:076d Microsoft Corp. LifeCam HD-5000
Bus 002 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 004 Device 002: ID 046d:c05a Logitech, Inc. M90/M100 Optical Mouse
Bus 004 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 003 Device 008: ID 0a5c:21e8 Broadcom Corp. BCM20702A0 Bluetooth 4.0
andyk_~/Downloads$ hcitool dev
Devices:
hci0 5C:F3:70:80:FF:DA
