You will also get problems with .wmv files, apparently due to some legal issues in Germany as to what can and what can't be included in the distribution.
I fixed all my problems by visiting http://xinehq.de/
and downloading the latest version of xine, together with all the required codecs. (In case you didn't know, Kaffeine is just one of many front ends for the xine media player.)
If you install the latest xine release, you will probably find that you have a couple of dependancies missing. You will be able to find them at http://rpm.pbone.net/
One word of warning, if you do this, Kaffeine and Xine will not be updatable through YOU in future.