Do
Code:
yum install xine-lib-extras-nonfree
if you use livna. If you use other repo, find a package non-free codecs for xine-lib. Xine-lib is now in extras (due to kaffeine and 64bit) and does not therefore include non-free codecs.
EDIT: ooops I mistyped the package name. Fixed now.