I had (I guess...) the exact same problem as Richard Grant using a headset Creative WP-350. It used to work fine on Ubuntu 16.04 and then the problem occurs when I switched to Ubuntu GNOME 17.04.
I was able to connect and pair the headset, and use it with "HFP/HSP" audio profile. When trying to switch to "A2DP" profile, it didn't work and indicate "Failed to change profile to a2dp_sink".
As doug indicated in his comment, the fix is to disable pulseaudio's bluetooth in gdm. Actually I don't understand the reason why pulseaudio's BT is enabled in Gnome Display Manager but there might be a good reason for that... if anyone can clarify this I'd like to understand.
So the fix is pretty easy, based on this link provided by doug, here is what I did:
Open a terminal window and type (This first point is user-dependant, the main info follow...)
then navigate to /var/lib/gdm3/.config/pulse
- Open default.pa if it exists or create it (I had to), as a regular text file.
Add the following lines in the file default.pa
# load system wide configuration
### unload driver modules for Bluetooth hardware
Save the file, close the Terminal window and reboot.