Ok, finalmente resolvi o problema. Eu consegui "reset" manualmente os fones de ouvido, pressionando um botão. Neste ponto, o Ubuntu não estava mais emparelhando automaticamente os fones de ouvido e eu fui capaz de reiniciar uma "nova conexão de dispositivo".
Então, não foi culpa do Ubuntu. :)