Are you running Win95 by any chance? Did you install Parallels Tools into the guest OS? What you are describing is exactly what happened to me running Win95 after I installed Parallels tools. Turn on virtual PC and it says "Starting Windows 95.." then goes to a black screen and stays there forever.
This is a known problem, and I have a thread about this a few pages down but noone seems to offer any advice. I worked around this by reinstalling Windows in a fresh virtual PC. Then, instead of installing parallels tools, I manually installed the video driver from thr vm tools disk image. i am able to boot up Windows with the improved video settings, but I am unable to manually install the Parallels sound driver (it's not on the disk image) so Im stuck with either no sound, or a generic soundblaster 16 driver that doesn't work well under Parallels (pops and crackles in the sound and freezes some aps when enabled). I guess there's no way o sucessfully run Win95 in Parallels, even though they claim it. All I know is I only want to run Windows to play a few games I have and I have no desire to buy a newer version of Windows to do so. When the trial period ends on my parallels demo i won't be purchasing the full version. Whats the point? It doesn't do what it says it does. They should offer an isolated download of their AC97 sound driver for manual install in Win95.