Tenho um palpite, a versão disponível por padrão da ffmpeg, que é a base do winff, é limitada por motivos legais. Mas existem algumas formas de contornar esse "problema".
Se você tem o ubuntu-restricted-extras para ativar as versões "unstripped" da bibliotecas você deve instalar: libavcodec-unstripped-52, libavutil-unstripped-49 and libavformat-unstripped-52 ou a versão "extra":libavcodec-extra-52. Um detalhe é que elas não suportam AAC e AMR.
Mas para resolver, "definitivamente", a melhor saída que eu vejo é adicionar o repositório medibuntu, já que você vai se deparar com vários outros problemas parecidos se não tiver ele. Para adiciona-lo, abra o terminal, copie e cole:
sudo wget --output-document=/etc/apt/sources.list.d/medibuntu.list http://www.medibuntu.org/sources.list.d/$(lsb_release -cs).list && sudo apt-get --quiet update && sudo apt-get --yes --quiet --allow-unauthenticated install medibuntu-keyring && sudo apt-get --quiet update
Depois disso você vai ter o repositório (lista em:/etc/apt/sources.list.d/medibuntu.list), as listas vão ser atualizadas e o repositório vai ser autenticado. A versão da biblioteca disponível no medibuntu é a mais completa, você só vai conseguir igual se compilar manualmente o ff e dependências. Para instalar:
sudo apt-get install ffmpeg libavcodec-extra-52
Fontes:
http://code.google.com/p/winff/wiki/UbuntuInstallation e
http://ubuntuforums.org/showthread.php?t=1117283