Eu tive um problema semelhante com meus fones de ouvido Jaybird X2 e foi isso que resolveu para mim:
Executar
sudo apt-get install pulseaudio-module-bluetooth
Em seguida, execute
sudo apt-get install ofono
Seguido por uma reinicialização.
Se eu entendi corretamente, há um bug conhecido com bluetooth em 16.04 e isso funcionou no meu caso. Deixe-nos saber se isso funciona.