I've been getting the "Bluetooth Not Functioning Correctly" message occasionally over the past two years. It seemed to get more frequent with the 7.0 software - happening about once a week. A reboot always fixes it. Then about 2 weeks ago, after upgrading to 2.9.40, I was having Bluetooth problems and I was trying various things to fix it before rebooting, and when I tried to delete the phone from the device list, that same error message came up briefly, then it went away, and it all started working. So I thought the new firmware had a workaround that whenever the Bluetooth subsystem gets into the bad state that results in that error message, it resets the BT system - a workaround, not a fix, but better than nothing. I asked the service centre about it but they didn't find a problem or fix anything. They upgraded me to 2.9.68, and since then I've seen the message a couple of times without the self-correcting. So I'm back to rebooting whenever this happens.
It's getting very annoying. Today a phone call came in while I was driving and I hadn't noticed that my phone hadn't connected to the car, so I couldn't answer it. This could be seen as a safety issue - an important call comes in that the driver really doesn't want to miss, BT is busted, and the driver frantically squirms around to pull his phone out of a pocket to answer it while driving...
I hope they fix this soon.