I was wrestling with bluetooth headsets off and on for years, with very limited success. I was able to get bluez/blueman working, pair the device, and even transfer audio using a command line program with a manually-entered device name. That did me no good, though. Only one application was able to find and use my headset (ALSA's discovery API doesn't seem to work with BT headsets) and even that app now fails in its most recent version. I have read that PulseAudio makes bluetooth headsets a bit easier, but since Pulse is not viable for me, the situation is still pretty bad.
Then I found this little gadget:
Jabra LINK 360 UC USB Adapter
It pairs with a bluetooth headset, but presents itself to the computer as a USB sound device instead of a bluetooth adapter. Every application I have is able to discover and use it because it doesn't require any bluetooth support in the operating system. It completely solved my problem.
Jabra is the only company that I'm certain makes such a thing. They also made one or two earlier models that can be found for less money. I chose the new one mainly because it's so tiny. I have heard that Creative makes something similar; perhaps their BT-D1 or BT-W2. If someone knows of others, please post links.