When I was on Ubuntu 18.04 I had the same issue, and after trying multiple thing online (related to bluez) I was able to make it work.
But I had to reinstall that Ubuntu and install a new Ubuntu 19.10. I had the 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 (in blueman) then immediately disconnects.
What diagnostics/logs should I provide?
