avidemux desapareceu dos repositórios depois de astutos; Resolvi adicionar repositórios confiáveis (porque é LTS) à minha sources.list.
Obviamente, isso instala a versão 2.5.4, mas a oficial; se você preferir um mais novo, o método ppa é melhor.
abra um terminal e dê:
sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak
(ou escolha o nome do arquivo que você preferir) para fazer backup de seu sources.list
então
sudo vi /etc/apt/sources.list
ou nano ou gedit ou ... o editor de que você gosta e adicione essa linha na parte inferior:
deb http://archive.ubuntu.com/ubuntu/ trusty main restricted universe multiverse
finalmente atualize e instale o avidemux com
sudo apt-get update; sudo apt-get install avidemux