O apt-get install não funcionou comigo. Mas andei procurando e consegui fazer o instalar o RealPlayer e fazer o Kaffeine abrir RMVB.
Segui esse tutorial.
http://gnutopia.net/2007/03/28/rmvb-no-ubuntu/Depois disso eu entrei no terminal, fui até a pasta onde eu tinha instalado e digitei ./realplay
Ele abriu normalmente, fez as perguntas de praxe e funcionou legal.
Fui então para o Kaffeine, mas ele ainda nao achava os kodecs.
Entao fui fuçar em Settings -> Xine Engine Parameters
Vi la em Decoders, que tem um campo pro caminho dos codecs do realplayer. Mas estava vazio.
Entao verifiquei o caminho onde eu instalei o RealPlayer pelo Tutorial, encontrei a pasta codecs e informei o caminho nesse campo.
No meu caso o caminho era apenas /home/subheaven/RealPlayer/codecs
e pronto.
Agora so falta eu descobrir o que aconteceu com meu som e como configura-lo direito no kaffeine.
Quando cheguei em casa ontem o Ubuntu tava sem som. Mexi nas preferencias de Audio e mudei o dispositivo para VIA 8235 e passou a funcionar no SO e no Beep Media Player.
Se alguem ja souber e puder me dar uma dica valeu. Mas vou continuar fuçando aqui.