Por razões discutido nesta questão , o" ffmpeg "no Ubuntu 12.04 é realmente fornecido pelo pacote libav-tools
; é por isso que remover o pacote ffmpeg aparentemente não faz nada.
Para realmente removê-lo:
sudo apt-get --purge remove libav-tools
sudo apt-get --purge autoremove
Nota: O conteúdo do arquivo deb do pacote 2.2 kB ffmpeg, conforme fornecido pela libav, simplesmente obtém o libav como dependências ...