Bluetooth Headset Connection Failed Error – Protocol Not Available

It is a known bug. Try rmmod btusb ; modprobe btusb. I have had to do it up to four times.

I have seen this with my Lenovo P50 with Intel 8260 wifi/bluetooth. Sometimes the bluetooth firmware doesn't load correctly at boot. Other times it just doesn't work.

So what worked for me is this -

1. Disconnect Bose headphones from Blueman-applet
2. run commands: sudo apt-get install pulseaudio-module-bluetooth pactl load-module module-bluetooth-discover
3. turn off Bose
4. turn on Bose and put Bose into paring mode
5. on Blueman applet right click and select setup new device
6. Select Bose headphones as device, then pair, then connect to hands free
7. finish pairing device and set it as trusted device
8. right click bose-applet > select recent device > select bose headphones
9. you should be connected! head to sound settings and change bose audio profile to a2dp sink instead of handset headunit (hsp...)

note: may be easier to select headphones in step 6 but I have not tried so