Todas as coisas parecem boas, mas o seu bluetooth provavelmente funciona apenas a cada três boot. Isso é o que funcionou para mim
echo "blacklist ath3k" | sudo tee /etc/modprobe.d/ath3k.conf
Em seguida, editamos um arquivo para carregar ath3k mais tarde no ciclo de inicialização
gksudo gedit /etc/rc.local
e acima da linha que diz exit 0
put sleep 10
e na linha abaixo que coloca modprobe ath3k
save, sai gedit e reinicia.
As últimas 3 linhas do arquivo /etc/rc.local
devem ser
sleep 10
modprobe ath3k
exit 0
Isso deve ajudar com o erro do firmware, pois há um problema de tempo com o xhci_hcd que impede que o ath3k carregue o firmware toda vez
NOTA: O problema é resolvido com o kernel 3.16.0-32 ou mais recente do Ubuntu sem as alterações acima por comentário 12 em relatório de bug e também corrigido agora em 3.13.0-47 por log de atualização veja * Bluetooth: ath3k: solução alternativa para o problema de compatibilidade com xHCI controlador - LP: # 1400215