Kdenlive relies on the MLT video engine.
By default, MLT only handles DV.
To have access to a wide variety of formats, you will need to install codecs.
Installed the audio and video packages listes on the following page:
http://kdenlive.org/user-manual/downloading-and-installing-kdenlive/inst... [1]
On some systems, you may need to install the package names 'ffmpeg-unstripped' instead of 'ffmpeg'.
Links:
[1] http://kdenlive.org/user-manual/downloading-and-installing-kdenlive/installing-source/installing-required-libraries