Eu encontrei este problema no meu Lenovo P51 rodando o Ubuntu 18.04, e descobri que o módulo pactl "module-bluetooth-discover" não estava carregando corretamente no momento da inicialização. Eu consertei o problema substituindo-o por "module-bluez5-discover" na minha configuração de pulsos.
Você pode testar isso executando: sudo pactl unload-module module-bluetooth-discover e sudo pactl load-module module-bluez5-discover
E tente reparar / reconectar seus dispositivos. Se funcionar, replique a seguinte configuração em sua configuração /etc/pulse/default.pa.
# 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
Minha suspeita é que esta é uma mudança que foi feita durante a troca do Unity para o Gnome e as configurações remanescentes permaneceram, deixando os módulos Bluetooth padrão atrás dos quais não carregam corretamente.
Depois de mudar para o bluez5, não tive nenhum problema e o Bluetooth é conectado sem reclamação no meu celular, mouse e fone de ouvido. :)
EDIT: Eu também segui vários passos mencionados aqui: O Bluetooth não funciona depois de sair do modo de espera, Ubuntu 18.04 LTS
Para replicar exatamente minha configuração, certifique-se de que apt-get install bluez blueman pulseaudio tenha todos os mesmos pacotes. Como foi sugerido no problema referenciado, acredito que isso foi causado pela atualização para 18.04 de 17.04.