Mine is not a Boot Camp VM. It is a disk image-based Windows XP guest OS that has been running fine for at least a year; only in the past month or so has this slowdown started. As additional info, I have 2GB in my Mac mini (running 10.5.4), and I give 256MB to XP.
I also have another Parallels session running: a Linux guest OS. This one usually doesn't take as long to launch as the XP guest does, but ever since the reinstall (as per my comment above), now both take several minutes to launch. Again, once it is launched, it runs fine - Linux runs at full speed, no problem.
Oh, one other interesting thing: the process that is eating my CPU while Parallels is hung during launch is WindowServer. And, I timed it - it is 2m30s, not literally 5 minutes. It just seems like it is that long. 
PS - edited to remove my choppy wording.
Last edited: Jul 18, 2008