Andei pesquisando um pouco e todos os lugares que encontrei como assistir arquivos .rmvb no Linux sugeriam duas soluções:

  • Instalar o RealPlayer no linux que pode ser baixado do site do realplayer.com
  • Substituir o pacote de codecs totem-gstreamer pelo totem-xine incluindo o w32codecs

Na primeira opção o vídeo ficava travando um pouco como que engasgando. Então ataquei a segunda opção mas fiquei com medo que pudesse parar de funcionar tudo o que já funcionava então tentei o seguinte:

Achei que deveria tentar instalar o w32codecs sozinho no totem-gstreamer e para minha surpresa funcionou!

Então facinho o que você tem que fazer é baixar o w32codecs daqui e instalá-lo.
Dois cliques Clica no botão instalar. Pronto! E ainda dizem que linux é complicado.