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?