A lot of people have experienced the dreaded "Bluetooth Not Available" problem on their Apple machines, and I just recently had it happen to me.
I've seen it before, and just rebooted to resolve it but this time I researched more.
Some people report that resetting the SMC will fix it. Some report it's a temperature thing. Odds are it can be many things, so this fix may not work for you.
One forum post reported that they hadn't noticed it, but they were using VMWare, and one of their VMs had taken control of the bluetooth device - simply unhooking it from the VM allowed it to be used in OS X again.
Imagine my chagrin when I noticed that was what had happened to me...so if you get this message and use VMWare, check your VMs to see if one of them grabbed the device. Disconnecting it will get you going again.