I had exactly the same problem when I recently installed Fedora Core 4.
check out : http://stentz.freshrpms.net/
and download Xine (a free media player).
It does the lot, although this version doesn't have any DVD support, (when I find the right plug-in) I will post it here...
You need to download the Xine Libraries and supplemental programs, which is easy to do as they are all RPM's you may need other libraries to be installed such as Libaa.so.1 etc, in which case they are all present at this site, just download and install the rpms.
Tip if looking for a library such as LibXVMCW, and you cant find it, try omitting the Lib bit and just searching fro XVMCW within the site. Failing that a quick search on google, just tapping in the library name is good enough, bringing up loads of results.
Hope this helps.