Si usaste un PPA tendrás que eliminarlo, después al avidemux instalado purgalo (la diferencia con desinstalar es que borra el .deb de la cache si aún estuviese, y la configuración), recarga la lista de archivos de los repositorios. Ya entonces tendrás solo el avidemux que estuviese en los repositorios oficiales.