This is the terminal only Mplayer ?
or the fedora default Gnome-mplayer gui
is gstreamer being used ?
If so are the "good, bad, and ugly" plugins installed ?
or did you install the very old 2006 all codec package or the newer 2011 all codec
for Fedora 18 see the mjmwired page
then go from there