I take no credit for the Raspberry Pi port side of things. As far as I'm aware, Bluetooth is working latest 16.04 Beta 2:
Re-reading the post again, it could be due to the upgrade process, as upgrading the Raspberry Pi between versions is not recommended.
In particular, check that your newly updated system is using these new versions and packages.
Updated BlueZ 5.37 with patches to support the Raspberry Pi 3 integrated Bluetooth.
Ubuntu MATE 16.04 now supports the on-board Raspberry Pi 3 Bluetooth and Wifi.
Updated to Linux 4.1.19.
Updated toraspberrypi-firmware
1.20160315-1.
Linux kernel can be checked by:
uname -r
Application versions can be checked with an apt tool like Synaptic.