Bluetooth audio device connected but not showing up in audio devices

I tried to load the module first but I got a Failure: Module initialization failed so you have to unload the module first:

pactl unload-module module-bluetooth-discover

and then load it again:

pactl load-module module-bluetooth-discover

After that I was able to see the audio device in audio settings.

I had the same issue here with Ubuntu Gnome 15.10 and 16.04. What helped me was adding read permissions for the gdm user on the pulseaudio bin.

sudo setfacl -m u:gdm:r /usr/bin/pulseaudio

after that restart pulseaudio (or restart your system)

pulseaudio -k

your bluetooth device should now be listed in the audio device list.