Sometimes when I connect my phone to my headset, the Bluetooth device will be listed as:
"Connected ( no media )"
When this happens, it uses the "Phone audio" profile. The "Media audio" profile (A2DP) will also have a checkmark, as if it were connected, but all sound is coming from the phone's speaker (see photo below). If I attempt to uncheck it, it will immediately recheck itself. When it is working properly, it will wait two seconds and disconnect.
Rebooting the headset, or disconnecting it manually doesn't solve the issue.