Minha solução alternativa para esse problema é remover o fone de ouvido da lista de dispositivos conhecidos (da configuração Bluetooth) e repetir o emparelhamento.
O fone de ouvido continuará funcionando conforme o esperado até que seja conectado a outra máquina (que também pode ser uma máquina virtual no mesmo computador). Então, novamente, temos que remover o dispositivo e repetir o pareamento.
Pode haver um problema com o emparelhamento sinmple seguro que ocorreu a partir de 11.10, mas deve ser corrigido no kernel 3.2.15 (veja bug # 931860 ). Tente se o desabilitar o SSP resolve seu problema também.