This has happened to me several times. I pair the headset and then when I push the button, it doesn't switch the audio. (Note the external jack overrides bluetooth audio, but I'm talking speaker). It connects, but then immediately disconnects even if something was playing through the speakers.

I lost the bluetooth config data but it was easy to repair all my devices.

I was going to reflash, but it seems that something in the /var/lib/bluetooth directory gets stuck in an invalid state. Under that directory is a directory with the adapter MAC/BT address. In that directory are about a dozen files.

I deleted the files and immediately rebooted (from a ssh or root shell, cd /var/lib/bluetooth/* (or use tab to get the address), then
rm *; reboot

The bluetooth subsystem will "remember" the bad data and write it out to this directory if you don't immediately reboot. After rebooting I just redid the pairing on my headset and everything worked.

Information in this directory is very sticky - even deleting a device doesn't erase every corresponding entry, and it doesn't seem to ever forget old scan results.

If it happens again, I'll see if I can determine which thing specifically was the problem. I may have paired two headsets before using either (I have a jawbone and a jawbone2, both have the device name as "jawbone"), or just having multiple once paired headsets.