Consegui finalmente corrigir este problema graças a esta resposta: link
Passo 1 - Liste seus dispositivos usb
lsusb
(Exibido por Bluetooth para mim)
Bus 002 Device 002: ID 0a5c:216f Broadcom Corp. BCM20702A0 Bluetooth
Passo 2 - Acesse link para fazer o download o driver convertido que corresponde ao seu ID acima. Para mim isso foi BCM20702A1-0a5c-216f.hcd (Clique no arquivo para baixá-lo)
Passo 3 - Copie o arquivo baixado para /lib/firmware/brcm
cd ~/Downloads
sudo cp BCM20702A1-0a5c-216f.hcd /lib/firmware/brcm
Passo 4 - Reinicie. Bluetooth deve estar funcionando agora.
Se você receber este erro ao conectar seu dispositivo de áudio Bluetooth:
Connection Failed: blueman.bluez.errors.DBusFailedError: Protocol Not available
Solução: link
sudo apt-get install pulseaudio-module-bluetooth
pactl load-module module-bluetooth-discover
E, em seguida, exclua o dispositivo dos dispositivos Bluetooth e faça o emparelhamento novamente.
Espero que isso ajude você a conectar seus dispositivos de áudio Bluetooth.