The good news
Kubuntu 8.10 works really well under the beta of Parallels Desktop 4. But it's not out yet, and we're not allowed to talk about it. You never heard it from me.
The bad news
Kubuntu 8.10 does not work under the current release version of Parallels Desktop 3. As soon as KDE4 attempts to start, the video mode goes wobbly and X restarts. kdm goes on an infinite start-crash-start-crash loop. It's great fun for the first thirty restarts or so.
So what's going wrong? I'm not entirely sure. You can start X by hand fine. And you can run X apps, so it wouldn't appear to be a video support problem. I've been tinkering with bits of the startkde script. The failure stems from the call to the ksmserver, which handles the majority of the bringing up the KDE session. It's around about here that my enthusiasm for debugging left, and I escaped back into Parallels betaland for a simpler experience.
Helpfully, if you try to start a failsafe X session under Parallels 3, it fails for entirely different reasons.