- Reset the SMC controller
- Reset the PRAM and NVRAM
- Repaired disk permissions
- Deleted Bluetooth preference files from my Home and System Library folders
And none of them have worked. Looks like my MacBook's Bluetooth controller is dead. Great.
Update: It's working again. Apparently all I needed to do was turn the computer off (at the plug), leave it overnight and turn it on again the following morning. How bizarre.

Thanks - got exactly the same issue with my MacPro 2.66 Nehalem. My feeling is that vmware has the problem of ‘occupying’ the bt device inside a vm and doesn’t give it back.
Resetting the SMC/PRAM/etc etc doesn’t work.
the only thing that does work is to physically switch off the machine !!
hope this confirmation helps other people as well
Thank you. Rebooting didn’t work — until I unplugged the machine first. Go figure!