It seems Parallels it is not supporting any MacOSX Lion Upgrades for their Desktop Solution version 10.5
encouraging (or I better say "forcing" ) their customers to upgrade to 10.6 as a solution because they claim this is the way to go for Lion.
Also seems there is a "Launcher" for 10.6 which is basically a quick patch which solves all the given issues, but what it was never told, that launcher also works on 10.5. As my own system can demonstrate.
The following should help to start your VMs.
sudo kextutil -q "/Library/Parallels/Parallels Service.app/Contents/Kexts/10.6/prl_hypervisor.kext"
sudo kextutil -q "/Library/Parallels/Parallels Service.app/Contents/Kexts/10.6/prl_hid_hook.kext"
sudo kextutil -q "/Library/Parallels/Parallels Service.app/Contents/Kexts/10.6/prl_usb_connect.kext"
sudo kextutil -q "/Library/Parallels/Parallels Service.app/Contents/Kexts/10.6/prl_usb_connect.kext"
sudo open -a "/Applications/Parallels Desktop.app"