I have a Mac Mini running OS X 10.5.7 and the latest firmware. The VM worked two days ago, I hadn't installed anything since.
Tried what you suggested to no avail. After shutting down my Mac and starting it again more than half an hour later, still got the same old message.
Thx for more suggestions.