My Qilive bluetooth headphones, which worked fine in 17.04, won't pair with my PC following a clean install on 17.10. Sometimes they show up very briefly in the list of detected devices before disappearing. I've had no problem pairing a smartphone, however.
The solution offered here didn't work as I can't pair the headphones if the computer can't see them.
Output from ls /var/lib/bluetooth is 00:C2:C6:14:A4:5A
Had a similar problem, but actually the solution you identified is indeed working. In order for Ubuntu to detect your device you have to make sure that this latter is in pairing mode with your pc's bluetooth off. Once the device enters in pairing mode you activate your bluetooh and the device will appear in the list.
I am using a Jabra elite bluetooth headset on Ubuntu Studio 19.10 this is what i had to do.hope it can help some persons. step 1 turn off pc bluetooth. step 2 enable bluetooth pairing on headset by shutting it off then turn back on holding button down until it says to turn on pairing mode on device which in this case is your PC. step 3 in your pc's blutooth dropdown menu click on add new device. step 4 in the window it should show your device after it finishes searching. step 5 click on your device. step 6 click next. it should pair and now you should have a working headset.
In my case, My Bluetooth Headphone is already connected with my phone. After I turn off my phone Bluetooth. My Laptop can detect the Bluetooth headphone.
I fixed same problem with the following procedure:
sudo rm /var/lib/bluetooth/cache/*