In my (Dutch) version of Ubuntu 9.04, I get the message (translated by me to English)
Needed:kdebase-runtime (>=4:4.2.4) but 4:4.2.2-0ubuntu1 is installed
Needed:kdelibs5 (>=4:4.2.4) but 4:4.2.2-0ubuntu5.2 is installed
A few weeks ago KDEnlive DID work on my PC. In the meantime, I've installed and later de-installed OpenShot.
I tried de-installing KDEnlive, restarting, removing KDEnlive and re-installing it, but it keeps giving problems.
Oh yes, I use the http://ppa.launchpad.net/sunab/ppa/ubuntu PPA repository. Maybe that has something to do with it?

I've noticed that on the sourceforge website, a more recent version of KDEnlive is available, albeit as a tar-file.
For a not-so-technical computer user as me, this is quite confusing.