Follow these instructions to get Tools working under 9.04
For i386 architecture, go to
http://packages.ubuntu.com/ and download the following (or just download my .zip archive of all necessary i386 packages here:
http://staff.washington.edu/rjsanyal/xorg 1.5.2 debs.zip)
x11-common_7.4~5ubuntu3_all.deb
xbase-clients_7.4~5ubuntu3_all.deb
xdmx-tools_1.5.2-2ubuntu3.1_amd64.deb
xdmx_1.5.2-2ubuntu3.1_amd64.deb
xnest_1.5.2-2ubuntu3.1_amd64.deb
xorg-dev_7.4~5ubuntu3_all.deb
xorg_7.4~5ubuntu3_amd64.deb
xserver-common_1.5.2-2ubuntu3.1_all.deb
xserver-xephyr_1.5.2-2ubuntu3.1_amd64.deb
xserver-xfbdev_1.5.2-2ubuntu3.1_amd64.deb
xserver-xorg_7.4~5ubuntu3_amd64.deb
xserver-xorg-core_1.5.2-2ubuntu3.1_amd64.deb
xserver-xorg-core-dbg_1.5.2-2ubuntu3.1_amd64.deb
xserver-xorg-dev_1.5.2-2ubuntu3.1_amd64.deb
xserver-xorg-input-all_7.4~5ubuntu3_amd64.deb
xserver-xorg-input-evdev_2.0.99+git20080912-0ubuntu6_amd64.deb
xserver-xorg-input-kbd_1.3.1-2ubuntu1_amd64.deb
xserver-xorg-input-mouse_1.3.0-1build1_amd64.deb
xserver-xorg-input-synaptics_0.15.2-0ubuntu7_amd64.deb
xserver-xorg-video-vesa_2.0.0-1ubuntu3_amd64.deb
xutils_7.4~5ubuntu3_all.deb
xvfb_1.5.2-2ubuntu3.1_amd64.deb
xlibmesa-gl-dev_7.4~5ubuntu3_all.deb
xlibmesa-gl_7.4~5ubuntu3_all.deb
xlibmesa-glu_7.4~5ubuntu3_all.deb
libglu1-xorg-dev_7.4~5ubuntu3_all.deb
libglu1-xorg_7.4~5ubuntu3_all.deb
Make sure they're all in one directory. Then, cd to this directory and invoke:
sudo dpkg -r xserver-xorg-video-all xserver-xorg-input-all
sudo dpkg -i *.deb.
Then install Parallels Tools using conventional instructions for Linux install. Worked for me and Kubuntu 9.04.
Hope this helps,
Rishi