Comment 10 for bug 1549163

2 Bernie:

I had similar issue with Xenial. Two things to be mentioned:

1) It was not clean OS install, Xenial was upgraded from 14.04
2) There were error messages, when I tried to choose HSP profile:

[pulseaudio] module-bluez5-device.c: Refused to switch profile to headset_head_unit: Not connected

So, I reinstalled the bluez package and the problem disappeared. Something like this:

sudo apt-get install --reinstall bluez