EDIT: Então eu finalmente consegui este trabalho: 1) Para tornar o Pulse Audio A2DP compatível, este pacote precisa ser instalado: pulseaudio-module-bluetooth. Mas depois disso ainda não é fácil fazer isso funcionar:
2) Applet Bluetooth Gnome vs. Blueman: - Eu não fui capaz de fazer este trabalho de forma confiável com o Blueman, mas descobri que isso acontece com o GNOME BLUETOOTH APPLET. Me deparei com essa solução quando decidi usar o Gnome Shell (3.4 no início) no meu Lubuntu, que obviamente veio com o applet Gnome Bluetooth (nome do pacote: gnome-bluetooth: Se você decidir instalá-lo sem o Gnome Shell, observe que ele irá puxar algumas bibliotecas gnome que ele precisa para funcionar). - Eu removi o problemático Blueman e emparelhei os dispositivos através do applet Gnome, o que levou ao sucesso do streaming A2DP, Pulseaudio via Bluetooth. Para que isso funcione, o BLUEMAN TEM QUE SER REMOVIDO, caso contrário, ele assumirá o controle do gerenciamento de todas as conexões Bluetooth. Quando atualizei minha instalação do Lubuntu de 12.04 para 13.04, o Blueman foi reinstalado e fez exatamente isso, e as coisas começaram a funcionar novamente depois que eu o removi.
3) Depois de instalá-lo (eu fiz via Synaptic) reiniciei PA
pulseaudio --kill
pulseaudio --start
mas isso pode ser desnecessário, tente no caso de você ter problemas no começo.
4) Para fazer a conexão com o fone de ouvido Sennheiser, eu preciso colocá-lo no modo de emparelhamento, ligando-o e segurando o botão on / off por um pouco mais, até que o LED pisca vermelho e azul (em oposição a modo de conexão - flash azul rápido - que normalmente seria suficiente para conectar o fone de ouvido a um dispositivo host que já o conhece: isso não funciona). Então, no miniaplicativo Gnome (deve lembrar-se do fone de ouvido após o primeiro pareamento), clique no botão "conectar" para o Sennheiser M100.
5) Pode ser necessário acessar as configurações de áudio e selecionar o M100 como dispositivo de saída, mas recebo áudio pelo fone de ouvido, e não pelos alto-falantes, mesmo que a placa de som do sistema ainda esteja selecionada.
Espero que isso funcione para você também, mas ainda assim: Quando você comprar hardware bluetooth para usar com seu sistema Ubuntu (ou derivativo), tente encontrar algo com suporte explícito ao Linux, de preferência drivers abertos!