Ubuntu 18.04 had the same issue, and after trying multiple thing online make it work.
Reinstall that Ubuntu and install a new Ubuntu 19.10. Same issues and looked up online again but nothing fixed it and I am frustrated at this point.
I can see the headphone, I try to pair it, sometimes it fails, sometimes it connects and shows the colored bars on the right then immediately disconnects.
What diagnostics/logs should I provide
I ran into this issue on my Lenovo P51 running Ubuntu 18.04, and I discovered that the pacts module “module-Bluetooth-discover” was not loading properly at boot time. I fixed the issue by replacing it with “module-bluez5-discover” in my pulse configuration.
You can test this by running:
sudor pact unload-module module-bluetooth-discover
sudo pactl load-module module-bluez5-discover
And try to repair/reconnect your devices. If it works, replicate the following configuration in your /etc/pulse/default.pa config.
# Modify: /etc/pulse/default.pa
# Comment out the following line
.ifexists module-bluetooth-discover.so
load-module module-bluetooth-discover
.endif
# Replace it with …
.ifexists module-bluez5-discover.so
load-module module-bluez5-discover
.endif
My suspicion is that this is a change that was made during the switch from Unity to Gnome and the leftover configurations remained, leaving the standard Bluetooth modules behind which don’t load correctly.
After switching to bluez5, I have since had no issues, and Bluetooth connects without complaint on my mobile phone, mouse, and headset. 🙂
EDIT: I also followed several steps mentioned here: Bluetooth doesn’t work after resuming from sleep, Ubuntu 18.04 LTS
To exactly replicate my configuration, make sure you apt-get install blues bluesman pulse audio to have all the same packages. As was suggested in the referenced problem, I believe this was caused by upgrading to 18.04 from 17.04.