Uma boa maneira de corrigir isso seria instalar o Blueman Bluetooth Manager.Após você instalá-lo Se, no entanto, acontecer de você obter a "Falha na conexão: Configuração do fluxo falhou" .Então, faça essa correção que eu encontrei em tuxdiary.com:
1.Edit /etc/bluetooth/audio.conf e descomente a seguinte linha:
AutoConnect=true
2. Execute o seguinte comando para instalar os pacotes mais recentes para o blueman e os módulos relacionados:
sudo add-apt-repository ppa:blueman/ppa
sudo apt-get update
sudo apt-get upgrade blueman
3. Execute o blueman-applet. Clique com o botão direito no miniaplicativo do painel e ligue o bluetooth.
4.A versão antiga do seu dispositivo bluetooth ainda estaria lá, remova-o. Clique com o botão direito no applet blueman-panel e selecione Setup New Device. Complete o assistente para o seu dispositivo.
5.Logout e login.