I recently upgraded to ubuntu 16.04 and got the same bug trying to connect my UE Boom 2. Some extensive googling shows that this is an ongoing issue with 16.04 since it was released in April 2016.
Nevertheless, I came across this discussion and managed to solve the issue with suggestions from Emmentaler and Brian Peacock.
Firstly with my UE Boom 2 connected, I went into "Sound Settings" and made sure the output "mode" was set to "Headset Head Unit (HSP/HFP)", NOT "High Fidelity Playback (A2DP Sink)". Making sure it was in the low quality output is the only way I can ensure a successful connection. Then I installed blueman
sudo apt-get install blueman and then rebooted.
From here, I clicked on the original bluetooth icon in the menubar, went to "UE Boom 2" and made sure the "connection" was set to OFF.
After that, I clicked on the new bluetooth icon in the menubar provided by blueman and selected "devices". The "UE Boom 2" appears in the window when it's discoverable. Now click "Setup..." at the top of the window. Given the choice of connection, under "Connect to:", I selected "Audio Sink". This took a couple of tries, but it worked eventually.
Once successfully connected, close the setup window and go back to the sound settings. You should now be able to switch the output mode to "High Fidelity Playback (A2DP Sink)" without losing audio. This is now the process I use to start up my UE Boom 2 each time I need to use it.
Your mileage may vary, but I hope this works for anyone who needs it. This bug has been driving me crazy all day.
TLDR: Connect using regular bluetooth, set connection to "On", set the output to "HSP/HSF" in sound settings (make sure that works), set connection to "Off". Then set up the device using blueman, connect it as an "Audio Sink". Now back into sound settings and change the output to "A2DP".