mopsmom1 - when you let the virtual PC boot into safe mode, what happens if you do a proper shutdown once it is running, then restart it?
Now the Mac part of the question - what OS X update method did you use?
There was a well known problem just using software update to download and run a "delta" upgrade (some had 170MB, some about 350MB for the download) which actually only downloaded something like 45MB then tried to run...
Have you tried the following?
1. Remove Parallels Tools from the PC - use the add/remove control panel in Windows.
2. Download the 10.5.6 COMBO update (a whopping 660MB+ download).
3. use the disc or .dmg file you installed Parallels from to uninstall it.
4. reboot.
5. log in, use disc utility to repair permissions, and then run the 10.5.6 combo updater.
6. let it run and reboot (possibly twice).
7. if paranoid (like me) - run repair permissions again when it reboots for the last time.
8. use the disc or .dmg file you have to re-install Parallels.
9. reboot.
10. log in and run up Parallels and your VM.
if that is all working, then it is up to you whether you re-install Parallels Tools on the virtual PC (you don't have to)
Good Luck! Let us know if this has helped at all.
P.S. I assume you went and grabbed the "proper" copy of Parallels build 5626 off the URL pointers in this forum - and used that to do a complete de-install/re-install.