Lo primero que hay que hacer es instalar ffmepg, bien desde Centro de Software o línea de comandos:
sudo apt-get install ffmpeg
Después hay que instalar PIP:
sudo apt install python-pip
Y ya por fin se instala Autosubsync:
pip install autosubsync
No tiene interface gráfica, hay que hacerlo desde línea de comando, por ejemplo: