Se anche voi come me usavate FFmpeg e reinstallando il nuovo sistema avete avuto la triste sorpresa, allora la soluzione più semplice è quella di utilizzare repository di terze parti, e nello specifico Jon Severinsson's FFmpeg PPA.
Per aggiungere repo e chiave basta dare il comando:
sudo apt-add-repository ppa:jon-severinsson/ffmpeg
poi basta dare un Update ed installare il pacchetto ffmpeg con i comandi:
sudo apt-get update sudo apt-get install ffmpeg