I had exactly the same symptoms but for a different set of steps. my problem turned out to be in /var/lib/bluetooth/[your-bt-mac-address]/linkkeys this file basically tracks the devices you've connected to. I had managed to edit this file and put a blank line at the top, and deleting this line and rebooting fixed everything. However it might be that any one of a number of odd problems can cause the bluetooth stack to fail to come up properly. Still, worth checking.