I've had similar problems recently with Ubuntu 9.10 and parallels tools. So when Parallels Desktop 5.0 came out I figured it would be worth trying.
It was.
My experience:
0. Upgrade to Parallels Desktop 5.0
0.1 Get networking to work. I'm still not sure why I have problems with this -- nobody else seems to.
1. I tried twice to install Parallels Tools without success. First of all, I saw no item on the disk with the name "install", so I was confused. I saw two items: installer.x86_32 and installer.x86_64. I tried the appropriate one and it ran, but it failed when it couldn't figure out where gcc was. It asked if it could download some stuff, I said okay, and it said I needed to install make, gcc and the kernel sources (all of which were already installed)
1.1 It turns out the image of the parallels tools CD was not the new one from Parallels 5.0
2. Uninstall Parallels Tools. The installer.x86_32 script gave me two options: Upgrade, and Remove. This time, I selected "Remove"
3. Unmount the parallels tools disk image
4. In the Parallels Virtual Machine menu, choose "Install Parallels Tools". This of course re-mounts the parallels tools image. But for me, this image was different than the one that was automatically mounted on my guest os. Of note, this image contains a script called "install" (just like the instructions explain)
5. Follow the instructions for installing parallels tools.
The installer does, indeed need to go download some stuff, so you do need networking to be functional.
Things seem to be working, but it is early

Click to expand...