As mentioned in the post before. I tried all the possible solutions. Nothing worked.
I even tried a reinstall of the OS. The problem still exists.
This is logged in the system log files at startup:
A command sent to the adapter has exceeded the time limit. The adapter has not responded. (twice)
And then:
The local Bluetooth adapter has failed for an unknown reason and is not being used. The driver has been unloaded.