Curioso, instalei aqui para testar usando um live-iso do Ubuntu 16.04.2 padrão (=Unity), o que significa kernel 4.8 e Xorg correspondente, previamente adicionando a ppa, a instalação foi de primeira, sem enroscar em nada e aparentemente está funcionando sem problemas, embora evidentemente não tenha testado exaustivamente, apenas chamei o programa e ele abriu normalmente, como se vê abaixo.
sudo add-apt-repository ppa:rebuntu16/avidemux+unofficial
sudo apt update
sudo apt install avidemux2.6-qt5
Note que precisa instalar a qt5 como mesmo o alerta anterior surgere ao se adicionar o repositório.