I also have the same problem and am looking for an answer.
I have Parallels set up so when it starts, it automatically goes into
COHERENCE mode.
If I shut down Parallels before turning off my Mac Pro, upon the next reboot,
I get a message that Windows was not shut down properly. I then have
to wait for a reboot of Windows as it stops at the black screen that asks
me whether I want to start Windows under normal conditions are not.
For now, I just log off Vista before shutting down Parallels.
