When turning on my bluetooth headset (Sony MDR-XB950N1) and the bluetooth automatically connects with my computer, it automatically selects the HSP/HFP profile which makes audio sound terrible. Moreover, when manually switching the profile to the A2DP sink through both Phonon and terminal (pacmd set-card-profile 3 a2dp_sink), it says that the A2DP sink is not available. However, when manually connecting the headset with the computer (this is what I'm doing temporarily to fix the issue but it's not a user-friendly experience), by disconnecting and reconnecting, the A2DP sink becomes available and is automatically used over the HSP profile.
That's problem in BlueZ/PulseAudio, not BlueDevil.