Na linha de comando:

mencoder -forceidx -ovc copy -oac copy -o file.avi p1.avi p2.avi

Onde -o é o nome do arquivo final a ser criado, os arquivos seguintes são as partes que serão usadas. Os arquivos devem ter as mesmas configurações de codecs, FPS entre outras coisas. Você não vai conseguir unir dois arquivos com propriedades completamente diferentes.

Para instalar o mencoder no Ubuntu:

sudo apt-get install mencoder