- 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