Eu tive exatamente o mesmo problema. Eu tentei vários métodos, incluindo o descrito aqui. Nada funcionou.
No entanto, encontrei uma maneira de corrigir isso.
Eu usei este tutorial para me levar até lá.
Acho que o problema é que eu não tinha o meu bluetooth le
definido como ativado. Qual é a forma como o arco é descoberto / conecta
sudo btmgmt le on
Isso pareceu consertar tudo.
Não tenho certeza do motivo da desativação. Fones de ouvido funcionam agora também.