I had the same problem after upgrading to 16.04. For me, there isn't a real fix, but I can get the speaker to work. I'm running Kubuntu so these steps are for KDE, and I'm not sure what the equivalent Unity steps are, but I'd imagine they're similar.
Here's what I did:
- Let the speaker connect.
- In your audio settings, change the profile to "Headset Head Unit (HSP/HFP)" or equivalent
Power off Disconnect the speaker
Restart the bluetooth service
sudo service bluetooth restart
Power the speaker back on and reconnect
- In your audio settings, change the profile back to "High Fidelity Playback (A2DP Sink)" or equivalent
A2DP should now work. So far, it seems that things only go wrong when I try to connect in A2DP mode. Until there is a real fix/workaround, I am going to try to remember to always switch to HSP/HSF mode before powering off or disconnecting the speaker.
It's sufficient to connect, switch to HSP/HFP mode, disconnect, reconnect, and switch back to A2DP mode. There is no reason to restart the bluetooth service.