For years I have been trying to get my bluetooth headphones to work on Debian and enlightenment e17. No, I hadn't tried very hard, but I had attempted this multiple times. By no means am I an expert on how bluetooth works and I understand that this howto will have you download a lot of heavy packages.

Now to the steps:
1) Install the following packages (I don't know if you need bluez or blueman):
sudo apt-get install gnome-bluetooth pulseaudio pulseaudio-module-bluetooth pavucontrol blueman bluetooth bluez

2) Create the file ~/.asoundrc
pcm.!default plug:pulse
pcm.pulse {
type pulse
}

3) Edit /etc/default/bluetooth to enable the following
HID2HCI_ENABLED=1
HID2HCI_UNDO=1

4) Reboot the system

5) Add systray to shelf (e17's requirement)

6) run gnome-bluetooth
sudo bluetooth-applet

7) Pair the headphones using the applet in the systray

8) Use Pulse Audio Volume Control to Select High Fidelity Playback (A2AP) and turn off the Built-in Audio Profile Off