I have easily paired my Sony SBH-20 headset with my Toshiba Portege notebook using Gnome Bluetooth on my debian 8.3 stable (debian jessie) system.

However connection could not be established that easily.
Whenever I turned the connection switch on in Gnome-Bluetooth it was instantly becoming off. The swiftness of this reaction made me think that there was something basically wrong with my Bluetooth configuration.
I have solved this problem basically following the Arch Wiki about Bluetooth Headset with a little adaptation for debian.
Firstly I installed pulseaudio-module-bluetooth package:
# apt-get install pulseaudio-module-bluetooth
Secondly, I restarted pulseaudio:
killall pulseaudio pulseaudio --check pulseaudio
At this point it could probably work directly using Gnome-Bluetooth, but I used following commands:
sudo systemctl start bluetooth bluetoothctl
Now in its own prompt:
power on
agent on
default-agent
connect {mac address of my already paired headset}
My Bluetooth headset connected successfully. Since then I have not experienced any problem with using Gnome-Bluetooth while turning my Bluetooth headset connection on and off.
I’m a US-based software engineer with a background in law. I share mostly practical tech notes here for my future self and anyone who finds them useful.
One of the things I’ve built is Masterlist: Focus & Tasks, a privacy-focused, local-storage-only task manager that offers focus tracking tied to tasks and projects, compatible with the Pomodoro technique.