I've already posted about installing libxine-extracodecs, back then for enabling MP3 support in Amarok.

When forwarding a mail containing some funny WMV videos to my wife, we found out she couldn't watch them with Kaffeine while I could. As it turned out, installing libxine-extracodecs also solved this issue.