Em vez de reiniciar o computador, você pode tentar:
sudo service bluetooth restart
Não é uma correção permanente, mas é mais rápida do que reiniciar. Eu nunca usei muito o bluetooth, mas descobri que, ocasionalmente, se estou usando wifi e faço algo funky, ele precisa ser reiniciado e preciso reiniciar o serviço de gerenciamento de rede para que ele reconheça as redes disponíveis atualmente.
Espero que isso ajude.