Comment 53 for bug 1490349

My laptop runs ubuntu 16.04. Linux: 4.4.0-93-generic
I tried to debug this issue by compiling bluetoothd from source code.
Surprisingly, this issue is fixed after executing newly compiled bluetoothd instead of /usr/lib/bluetooth/bluetoothd.
Steps to build and run newly compiled bluetoothd is listed below.

sudo systemctl disable bluetooth.service
sudo systemctl stop bluetooth.service
* make sure bluetoothd started by systemd is stopped.
sudo systemctl status bluetooth.service

* build bluetoothd
mkdir test
cd test/
apt-get source bluez
cd bluez-5.37/
sudo apt-get install libglib2.0-dev
sudo apt-get install libdbus-1-dev
sudo apt-get install libudev-dev
sudo apt-get install libical-dev
sudo apt-get install lib64readline-dev
sudo apt-get install libreadline-dev
./configure
make
cd src/
ls
sudo ./bluetoothd -n
bluetooth may work now.

The drawback is that you have to start bluetoothd manually after reboot.
Good luck.