Well, the mlt stuff seems to be alright. I'm running out of ideas here. Time to start from scratch, I guess:

1) remove the PPA repository for kdenlive; then update the package archive
2) purge everything libmlt, this will also remove packages that depend on it, but that's exactly what we want
3) remove any leftover kdenliverc and kdenlive directories under .kde
4) purge frei0r-plugins, swh-plugins
5) do a sudo apt-get autoremove --purge
6) install kdenlive (this will be the 0.7.3 package), try it out, if it works
6a) add swh-plugins, frei0r-plugins back in one by one to see if it works

If this still doesn't work, you could try the kdenliveBuilderWizard. And if this still doesn't work, I don't know what will.

Could you tell me what "Purge" means? :o

--purge means that any configuration files of a package are removed as well, not just binaries and other data. (See man dpkg)

EDIT: It's recommended to check the list of packages that are selected for removal when using autoremove!

Wow, thanks! It works now. ^__^
I purged everything you told me to, and then installed kdenlive again (0.7.3). Now it's working =)