SIM! Está funcionando de novo! Não sei o que consertou:
Eu fiz downgrade de bluez (4.96) e pulseaudio (2.1-0) como recomendado neste artigo: link
O Bluez se recusou a instalar sem o libudev0, então eu o instalei como sugerido neste artigo: link
Antes de fazer o downgrade, verifiquei se o libudev0 sozinho faria o truque, mas não. O downgrade quebrou tudo totalmente sem nenhum dispositivo de áudio selecionável como resultado.
Então eu deixei o Ubuntu procurar por atualizações e aceitei atualizar o bluez, pulseaudio e tudo sugerido (não havia atualizações na sugestão antes do downgrade). Eu permiti que os arquivos confs fossem sobrescritos. Então reiniciei o pulseaudio ("sudo service pulseaudio restart" no terminal). E AGORA FUNCIONA !!!
Só quero acrescentar que tentei várias vezes desinstalar e reinstalar o bluez e pulseaudio antes disso e praticamente qualquer coisa relacionada ao bluetooth.
Talvez alguém consiga descobrir o que resolveu o problema, caso contrário, sugiro que alguém tenha os mesmos problemas que eu para fazer o que eu fiz passo a passo.