Tenha o mencoder e o lame instalados em seu sistema e passe o seguinte comando em um terminal (console):

# mencoder -oac mp3lame -lameopts cbr:br=64:vol=2 -srate 22050 -ovc xvid -sws 1 -xvidencopts bitrate=500:max_key_interval=120:vhq=4 -ofps 30 video.rmvb -o saida.avi

Substitua o video.rmvb pelo arquivo de entrada, isto irá gerar um arquivo chamado saida.avi no diretório atual.

Fonte: http://carlrobers.wordpress.com/2008/12/20/convertendo-rmvb-para-avi-no-linux/