Umm, this might be a bit painful, but give it a go:
1. uninstall Parallels Tools from your running VM, then reboot the VM, check it is gone and shut down the VM.
2. Uninstall Parallels from the last install image/disk you used. Let that all happen, reboot the Mac and do a repair permissions from Disk Utility. Then shutdown the Mac.
3. Flash the PRAM when cold booting your Mac (hold: "option command P R" and wait for the 3rd boot chime/gong then release those 4 keys).
4. Let the Mac boot, then using your last install image/disk, re-install Parallels.
5. Reboot and do another permissions repair.
6. Run up the VM - verify it is working as though "out of the box"
7. If happy, do a clean re-install of Parallels Tools.
That is sort of how I've done my 3 upgrades (5160, 5582 and 5584) of Parallels since I first installed v3.0 off the disk. I have had no problems...
YMMV
