Yup. Spaces plist is the culprit (~/Library/Preferences/com.apple.spaces.plist). After deleting it, and then rebooting, my Fusion VM auto-starts up again.
Wow.
