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