Bluetooth - Connection Failed: blueman.bluez.errors.DBusFailedError: Protocol Not available

I'm trying to add a BlueParrott B-250XT+ bluetooth headset on a Thinkpad X230 tablet running Ubuntu 16.04 with its hardware bluetooth adapter.

The adapter works - meaning it detects/sees the headset. However, when connecting to the headset it initially connects, then this error pops up:

Connection Failed: blueman.bluez.errors.DBusFailedError: Protocol Not available

Afterwards, the Headset disconnects and future connections are impossible - this is some sort of failure/error that causes the bluetooth to be unresponsive afterwards.

I have Pulseaudio installed and I have bluetooth set to load after X11 (this is what got me this far - to the point I can connect). But, as mentioned, the device gets dumped shortly after connection.

The solution from this article worked for me:

sudo apt-get install pulseaudio-module-bluetooth
pactl load-module module-bluetooth-discover

Then delete the device from bluetooth devices and pair it again.

If it works, you can consider adding the second command to your startup settings, so that you don't have to run it again after every reboot.

If it doesn't work, try restarting pulseaudio:

pulseaudio -k
pulseaudio -D

What did work for me was this: (as pointed above by Sebastian Widz)

$ sudo apt-get purge pulseaudio  
$ rm ~/.config/pulse && sudo killall pulseaudio  
$ sudo apt-get install pulseaudio  
$ pulseaudio --start

The above to ensure pulse is working first.
Then, this one, which is a bit weird that doesn't come by default with pulseaudio itself:

$ sudo apt-get install pulseaudio-module-bluetooth  
$ pactl load-module module-bluetooth-discover  

A bit redundant I know, but these were the exact steps that worked for me 10 minutes ago.
But OK, at least it works now :)