Eu tive o mesmo problema com o Ubuntu 13.04, com um Logithech Boombox UE. No meu caso, a solução foi editar o arquivo /etc/bluetooth/audio.conf
.
Na seção [General]
add:
Disable=Socket
Enable=Source
Isso deve fazer a conexão funcionar. No entanto, o som está falhando e eu tive que adicionar outras modificações ao arquivo.
Na mesma seção, adicione:
SCORouting=PCM
AutoConnect=true
Na seção [Headset]
add:
HFP=false
SBCSources=1
MPEG12Sources=0
Isso resolveu o problema para mim.
Espero que ajude.