Add Freshrpms Updates and DAG's repositories and then try installing totem-xine and totem-gstreamer
http://fedoranews.org/mediawiki/index.php/Fedora_Core_4_Linux_Installation_N...: Refer this ^ to add freshrpms into your YUM repo list
http://dag.wieers.com/home-made/apt/FAQ.php#B4 Refer this ^ to ass DAG into your YUM repo list
Why are you installing FC4? is it only for Multimedia?