Tente isto:
sudo apt-get install --reinstall bluez
Resposta atualizada:
- Desative e reative seu dispositivo bluetooth com o disco rígido do computador (interruptor ou botão)
- Vá para "Configurações do sistema" > > 'Bluetooth' e ative 'Mostrar status do Bluetooth na barra de menu' ...
- Defina 'Bluetooth ON' na barra de menus e reinicie o seu sistema ...