After updating pulseaudio to 1:8.0-0ubuntu3.1 on Xenial, bluetooth audio stopped working. After attempting a re-pairing it seems like bluetoothctl connects to the device, then disconnects.
[NEW] Device 04:52:C7:09:F9:C1 The Ox
[CHG] Device 04:52:C7:09:F9:C1 Connected: yes
[CHG] Device 04:52:C7:09:F9:C1 Connected: no
[CHG] Device 04:52:C7:09:F9:C1 Connected: yes
[CHG] Device 04:52:C7:09:F9:C1 Connected: no
[CHG] Device 04:52:C7:09:F9:C1 Paired: yes
[CHG] Device 04:52:C7:09:F9:C1 Connected: yes
[CHG] Device 04:52:C7:09:F9:C1 Connected: no
[CHG] Device 04:52:C7:09:F9:C1 Connected: yes
[CHG] Device 04:52:C7:09:F9:C1 RSSI: -73
[CHG] Device 04:52:C7:09:F9:C1 Connected: no
[CHG] Device 04:52:C7:09:F9:C1 Connected: yes
[CHG] Device 04:52:C7:09:F9:C1 RSSI: -60
[CHG] Device 04:52:C7:09:F9:C1 RSSI: -75
[CHG] Device 04:52:C7:09:F9:C1 Connected: no
[CHG] Device 04:52:C7:09:F9:C1 RSSI: -58
This used to work on 1:8.0-0ubuntu3 and the update on Thu, 03 Nov 2016 16:58:35 +1100 to 1:8.0-0ubuntu3.1 broke it. Attempting to revert the update will try to downgrade my gdm and gnome-shell.