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.
UPDATE:
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.
/// pulseaudio[1942]: [pulseaudio] module-bluez5-device.c: Default profile not connected, selecting off profile /// bluetoothd[790]: /org/bluez/hci0/dev_0C_A6_94_EE_96_4E/fd0: fd(24) ready /// pulseaudio[1942]: [pulseaudio] bluez5-util.c: Transport TryAcquire() failed for transport /org/bluez/hci0/dev_0C_A6_94_EE_96_4E/fd0 (Operation Not Authorized) /// kernel: [ 842.519817] input: 0C:A6:94:EE:96:4E as /devices/virtual/input/input15
– MaxAuray Apr 27 '16 at 07:27