Exactly what media player is it?
If you know what codecs you need, you can usually find a package that provides them. What are you trying to watch, some sort of Matroska thing? Perhaps WMV? If a normal mpeg doesn't play, your system is fucking broken.