Totem puede funcionar usando los plugins de Gstreamer o los de Xine. Aunque es posible reproducir videos con codecs propietarios usando Gstreammer, te recomiendo que uses el plugin de Xine. SImplemente ejecuta:
(Estoy suponiendo que estás usando la configuración de yum que se menciona en la FAQ de Fedora y que tienes habilitado el repositorio livna.)
De todas formas, creo que deberías instalar varios reproductores de video (xine, mplayer, vlc) y probar para ver cuál te funciona mejor.