Use o automatix para instalar os codecs, pois ele vai trocar o "totem-gstreamer" pelo "totem-xine" (vc. pode instalar o pacote totem-xine também pelo APT, mas não sei se assim dá certo).
Usando o Gutsy, o Totem já deve tocar rmvb. Usando o Feisty, ainda é preciso uma pequena correção.
E a correção consiste em editar o arquivo "~/.xine/catalog.cache" mudando "decoder_priority=5" para "decoder_priority=10" na configuração do plugin do real audio, que está abaixo da linha “xineplug_decode_real_audio.so”.
Ah, veja também se vc. tem instalado o pacote "w32codecs".
Fui.