Totem/ Totem-xine
 

Running Totem under FC3 produces the following

** (totem:14483): WARNING **: don't know how to handle video/mpeg, systemstream=(boolean)true, mpegversion=(int)1

I have installed every package apparently required, but the program refuses to play anything. I ran through a full installation of totem-xine, still without success.

Can anyone help, or is there another simple movie player that would be a better choice?

There's a much, much better player then Xine and Totem. It's called mplayer. You can easily install it using apt-get or yum too. Search the forum after apt-get and mplayer if you don't want to install from source. Though, I highly recommend you to compile from source :)