Eu tive o mesmo problema desde o Ubuntu Gnome 15.04. Eu tenho um alto-falante fotivo que suporta os modos A2DP e fone de ouvido. Ele funciona com meu telefone Android, com o mesmo computador no Windows 10 e com outro computador rodando o Fedora 23. Acredito que ele também funcionou com o Linux Mint no mesmo hardware. Mas nunca funcionou com o Ubuntu Gnome; ele se conecta como fone de ouvido e o protocolo A2DP está desativado.
Edit: Eu apenas tentei as instruções aqui , e elas funcionaram para mim; meu alto-falante está atualmente conectado em A2DP e reproduzindo em estéreo de alta qualidade. No entanto, eu já tentei antes, e eles não funcionaram em versões anteriores do Ubuntu, então sua milhagem pode variar.
Isso ainda é menos que ideal, porque agora não poderei alternar para o modo fone de ouvido para usar o microfone.
Editar 2: falei cedo demais. Eu apenas reiniciei a máquina para ver se as mudanças iriam continuar, e eles não - o fone de ouvido nem se conectaria. Comecei a trabalhar em alguns dos passos que encontrei: recarreguei o módulo bluetooth-discover do pulsaudio, e isso não funcionou; Eu reiniciei o serviço bluetooth e agora ele funciona. Então, tente isso e veja se você obtém os mesmos resultados.
pactl unload-module module-bluetooth-discover
pactl load-module module-bluetooth-discover
sudo systemctl restart bluetooth
Não sei qual dessas etapas está realmente resolvendo o problema. Além disso, note que eu não matei e reiniciei o próprio pulso, pois isso parece confundir os aplicativos já em execução.