When I add a clip (mp4 file), Kden replies "clip is invalid. Will be removed from the project." The only option is to press "OK", and then the file is indeed removed from the clip window.

These files have no problem being played on other video players (like VLC, Windows Media Player etc.).

Any advice?

NOTE: I just reinstalled KDen. This problem had also occurred when I first installed KDen, but it eventually went away without me doing anything (that I'm aware of, that is).

Did you install the correct version of ffmpeg? There's a couple of threads about that in here.