Para mim, depois de dois dias de busca sem sorte.
Eu queimei uma imagem do Ubuntu em um pen drive, entrei no modo Try.
Testado Bluetooth e funciona e poderia encontrar dispositivos e par.
Então eu instalei uma nova imagem do Ubuntu no meu HardDisk tentei instalar todos os programas instalados na instalação antiga até aquele momento em que descobri que o Bluetooth parava de funcionar
Eu imaginei que instalei uma ferramenta chamada TLP para gerenciamento de energia, quando a removi via apt remove tlp
e reinicializei, o Bluetooth funcionou e pude encontrar outros dispositivos!
Talvez o TLP precise ser configurado de alguma maneira para funcionar bem com o Bluetooth
Espero que isso possa ajudar você
Atualização:
Instalei a versão mais recente do TLP e agora o Bluetooth funciona sem problemas.
Lançamentos de TLP no Gihub: aqui
Faça o download da última versão descompactada
cd TLP-1.0
# use checkinstall so that you can remove it anytime
sudo checkinstall
Use o PPA para obter o release mais recente
sudo add-apt-repository ppa:linrunner/tlp
sudo apt update
sudo apt install tlp
E reinicie.