Eu tive o problema semelhante.
Eu resolvi isso indo ao Ubuntu Software Center e instalando os seguintes pacotes:
GStreamer extra plugins
GStreamer ffmpeg video plugin
GStreamer plugins for mms, wavpack,qucktime,musepack
Depois de instalar todos esses pacotes, eu pude reproduzir vídeo sem problemas.
Tanto quanto eu entendo o sistema deve ser capaz de instalar os pacotes dependentes por si só, mas há um bug