Comment 31 for bug 1181106

I have the same problem and the solution for me was to manually change the profile. This post on the Ubuntu forums was very helpful:

In essence, you need to run the following command to switch profile to a2dp:

sudo pactl list cards short
sudo pactl set-card-profile <card name from above step> a2dp

The interesting thing for me is that when I initially connected the Logitech Mini Boombox, it was found with no problems and it worked flawlessly. However, I forgot to connect the laptop to a power source and when it finally shutdown in the night, I could not get it to work again in the morning - not even after purging and reinstalling all bluetooth related packages as well as pulseaudio. In the end, the two commands above worked just fine.