try downloading vlc mediaplayer...
sounds like you have crappy decoder plugins in media player ( and as such also in most other non ms players)
vlc mediaplayer has his own decoders, and as such is not affected by any crappy decoders in windows
http://www.videolan.org/vlc/
and it also has decodes for just about any encoding that's out there..