I too encountered this problem: Bluetooth audio stopped working after I upgraded to 16.04.

Running pulseaudio -v, I saw my headphones connect, then the TryAcquire() error message from the subject line of this bug:

I: [pulseaudio] module.c: Loaded "module-bluez5-device" (index: #21; argument: "path=/org/bluez/hci0/dev_00_18_09_24_DD_95").
I: [pulseaudio] module-card-restore.c: Card bluez_card.00_18_09_24_DD_95 profile a2dp_sink became available, activating.
I: [pulseaudio] module-bluez5-device.c: Transport /org/bluez/hci0/dev_00_18_09_24_DD_95/fd3 acquired: fd 30
I: [pulseaudio] module-bluez5-device.c: SBC parameters: allocation=0, subbands=1, blocks=3, bitpool=53
I: [pulseaudio] module-device-restore.c: Restoring volume for sink bluez_sink.00_18_09_24_DD_95: front-left: 54407 /  83%,   front-right: 54407 /  83%
I: [pulseaudio] module-device-restore.c: Restoring mute state for sink bluez_sink.00_18_09_24_DD_95: unmuted
I: [pulseaudio] sink.c: Created sink 1 "bluez_sink.00_18_09_24_DD_95" with sample spec s16le 2ch 44100Hz and channel map front-left,front-right
I: [pulseaudio] sink.c:     bluetooth.protocol = "a2dp_sink"
I: [pulseaudio] sink.c:     device.description = "MDR-AS800BT"
I: [pulseaudio] sink.c:     device.string = "00:18:09:24:DD:95"
I: [pulseaudio] sink.c:     device.api = "bluez"
I: [pulseaudio] sink.c:     device.class = "sound"
I: [pulseaudio] sink.c:     device.bus = "bluetooth"
I: [pulseaudio] sink.c:     device.form_factor = "headset"
I: [pulseaudio] sink.c:     bluez.path = "/org/bluez/hci0/dev_00_18_09_24_DD_95"
I: [pulseaudio] sink.c:     bluez.class = "0x240404"
I: [pulseaudio] sink.c:     bluez.alias = "MDR-AS800BT"
I: [pulseaudio] sink.c:     device.icon_name = "audio-headset-bluetooth"
I: [pulseaudio] sink.c:     device.intended_roles = "phone"
I: [pulseaudio] source.c: Created source 1 "bluez_sink.00_18_09_24_DD_95.monitor" with sample spec s16le 2ch 44100Hz and channel map front-left,front-right
I: [pulseaudio] source.c:     device.description = "Monitor of MDR-AS800BT"
I: [pulseaudio] source.c:     device.class = "monitor"
I: [pulseaudio] source.c:     device.string = "00:18:09:24:DD:95"
I: [pulseaudio] source.c:     device.api = "bluez"
I: [pulseaudio] source.c:     device.bus = "bluetooth"
I: [pulseaudio] source.c:     device.form_factor = "headset"
I: [pulseaudio] source.c:     bluez.path = "/org/bluez/hci0/dev_00_18_09_24_DD_95"
I: [pulseaudio] source.c:     bluez.class = "0x240404"
I: [pulseaudio] source.c:     bluez.alias = "MDR-AS800BT"
I: [pulseaudio] source.c:     device.icon_name = "audio-headset-bluetooth"
I: [pulseaudio] source.c:     device.intended_roles = "phone"
I: [bluetooth] core-util.c: Successfully enabled SCHED_RR scheduling for thread, with priority 5.
I: [bluetooth] module-bluez5-device.c: Transport /org/bluez/hci0/dev_00_18_09_24_DD_95/fd3 resuming
I: [pulseaudio] module-always-sink.c: A new sink has been discovered. Unloading null-sink.
I: [pulseaudio] card.c: Changed profile of card 1 "bluez_card.00_18_09_24_DD_95" to a2dp_sink
I: [pulseaudio] module-card-restore.c: Storing card profile for card bluez_card.00_18_09_24_DD_95.
I: [bluetooth] bluez5-util.c: Transport /org/bluez/hci0/dev_00_18_09_24_DD_95/fd3 auto-released by BlueZ or already released
I: [pulseaudio] module.c: Unloading "module-null-sink" (index: #14).
I: [pulseaudio] sink.c: Freeing sink 0 "auto_null"
I: [pulseaudio] source.c: Freeing source 0 "auto_null.monitor"
I: [pulseaudio] module.c: Unloaded "module-null-sink" (index: #14).
I: [pulseaudio] module-card-restore.c: Card bluez_card.00_18_09_24_DD_95 profile a2dp_sink became available, activating.
E: [pulseaudio] bluez5-util.c: Transport TryAcquire() failed for transport /org/bluez/hci0/dev_00_18_09_24_DD_95/fd3 (Operation Not Authorized)

Digging into the source, it looks like TryAcquire() simply tries to send a message over the DBus.  A little digging led me to /etc/dbus-1/system.d/bluetooth.conf, which contains the following:

  <!-- allow users of bluetooth group to communicate -->
  <policy group="bluetooth">
    <allow send_destination="org.bluez"/>
  </policy>

  <policy at_console="true">
    <allow send_destination="org.bluez"/>
  </policy>

I tried adding myself to the bluetooth group, restarted, and boom! now I have audio.

So it appears something changed between 15.10 and 16.04 w.r.t. the DBus permissions - the behavior of at_console perhaps?  The bluez package owns the above config file, so I added it to this bug.