The answer is (possibly) to check you have the latest gstreamer and appropriate codecs installed.
yum install gstreamer installs the main gstreamer libraries etc. You'll also need the plugins (codecs) for each format. Because some of these are of dubious legal status - ie. there's a possibility of patent/copyright infringement, they aren't hosted on the main redhat repositories. You'll need to make sure that the livna repos are available to yum (eg. by following the instructions in the Fedora FAQ), if you want to install them.
The output from
yum list (livna repos only)
Code:
gstreamer.i386 0.8.7-4.FC3.0
gstreamer-ffmpeg.i386 0.8.3-0.1.fc3.fr
gstreamer-plugins.i386 0.8.5-1
gstreamer-plugins-extra-audio.i386 0.8.6-2.1.fc3.fr
gstreamer-plugins-extra-dvd.i386 0.8.6-2.1.fc3.fr
gstreamer-plugins-extra-video.i386 0.8.6-2.1.fc3.fr
gstreamer-plugins-mp3.i386 0.8.5-0.lvn.2.3
This is also the reason these aren't installed "out-of-the-box". RedHat et al. did not want to expose themselves to litigation or demands-for-payment from the copyright holders on various codecs and code. It's the same reason mp3 support is not available "out-of-the-box", and non-Free (as in speech) software is not included. You may hate RedHat for "crippling" the distro - but it's hard to run a business when you're in court every day, and have lawyers overlooking your coders (unless you're a much richer corporation - no names!).