¿Qué distribución usas?
En mi caso (Fedora Core 6) la instalación de kplayer (basdado en mplayer) y kaffeine (basado en xine) instaló por dependencias otros paquetes como xvidcore (para divx) y lame (para mp3). Si eso no es suficiente, puedes descargar el
paquete de codecs "essential" desde la web de mplayer y luego descomprimirlo. Eso creará un directorio llamado "essential-<version>"; dentro de ese directorio encontrarás (casi) todos los codecs que puedan faltarte. Copia esos archivos (NO el directorio, sólo los archivos) a /usr/lib/win32; si esa ruta no existe, créala.