Son los códecs de audio, a mi también me pasa lo mismo, ALSA y PulseAudio no funcionan adecuadamente con tarjetas de sonido Audigy, instala alsa y pulseaudio desde http://packages.ubuntu.com descarga las versiones de Hardy Heron, así solucione el problema.
También me pasaba usando Xine como backend, no solamente con Gstreamer.
Te recomiendo ampliamente usar mplayer, es más ligero y óptimo, también reproduce de todo.
Si tienes experiencia, te recomiendo bajarlo desde SVN (o el source code desde la página) y compilar/instalar manualmente para tener una instalación aún más optimizada.
Si te sigue dando problemas, corre totem desde consola y fijate en los posibles errores que te dará ahí y los pegas aquí, así podríamos ayudarte mejor; abre la terminal y ejecuta:
~$ totem /ruta/a/tu/archivo.***