Existe varias maneiras você pode fazer pelo mencoder(linha de comando) ou pelo Avidemux.
Mencoder: Instale ele pelo Synaptic mesmo. Abra o terminal, entre na pasta onde esta o vídeo que você quer converter, e cole esse comado abaixo.Um exemplo do comando para converter em mpeg:
conversão de arquivo para dvd-ntsc
mencoder nome do seu video.xxx -oac lavc -ovc lavc -of mpeg -mpegopts format=dvd -vf pp=lb,scale=720:480,harddup -srate 48000 -af lavcresample=48000 -lavcopts vcodec=mpeg2video:vrc_buf_size=10000:vrc_maxrate=9800:vbitrate=5000:keyint=18:acodec=ac3:abitrate=192 -ofps 30000/1001 -o video_dvd_ntsc.mpg
Pelo Avidemux é mais simples ainda é só instala-lo pelo Synaptic mesmo. Depois de instalado abra o programa, abra o vídeo que você quer converter, no menu a esquerda escolha mpeg, em configure deixe a opção two pass ativada, se você quizer você pode escolher um encoder para o áudio no menu a equerda. Depois é só mandar salvar o vídeo.