How can I enable High Fidelity Playback (A2DP Sink) for my Bluetooth Headset?

You need to make sure PulseAudio believes your device is connected - even if you think it is.

Run the command bluetoothctl and look at the devices connected. I have 2:

[NEW] Controller 00:1A:7D:DA:71:11 Hairy16 [default]
[NEW] Device E8:07:BF:12:FA:4A AUSDOM AH861
[NEW] Device 90:B9:31:77:B7:78 Tim's iPhone

type the command connect <ADDR>, where <ADDR> is the 12 letter address of your device - e.g. E8:07:BF:12:FA:4A. You should see the following:

[bluetooth]# connect E8:07:BF:12:FA:4A 
Attempting to connect to E8:07:BF:12:FA:4A
Connection successful
[DEVICE NAME]#

Then you can change the profile successfully.

This is a bug in current 8.0 in 16.04. See more here: https://bugs.launchpad.net/ubuntu/+source/pulseaudio/+bug/1574324

I'm currently helping the devs figure out what patch is broken. In the meantime, write an email to me from launchpad, and I will help you with a version without those patches.