Melhor conversor de vídeos para Ubuntu? Bom, vai depender do formato de destino ao qual deseja realizar a conversão, e do seu propósito com isso (se quer apenas converter, ou se pretende editar o vídeo de algum modo).
Se você pretende converter os arquivos para MP4 com vídeo em h264 e áudio em AAC, e quer fazer isso com a melhor qualidade de imagem, então eu sugiro pra você o HandBrake (
http://handbrake.fr/).
É um programa Open Source disponível para Windows, Linux e Mac, projetado para encodar vídeos para MKV ou MP4 apenas. Além disso, o programa é totalmente independente, não sendo preciso instalar o ffmpeg ou mencoder dos repositórios antes. Utilizo ele bastante para converter filmes e séries para MP4, para poder assistir na TV LCD Sony Bravia de 42'' do meu pai, que consegue tocar vídeos em MP4 a partir de pendrives ou HDs externos. Através dele, também consigo embutir legendas no vídeo, dado que o arquivo de origem seja MKV, e que a legenda interna esteja em formato SSA.
Caso o formato seja outro, e você queira apenas converter, então há outras soluções como o Mobile Media Converter, o Aristo e o Transmageddon.
Caso o formato seja outro, e você queira editar, você pode usar o Avidemux (paliativo do VirtualDub para Windows), PiTiVi ou Openshot.