Você deve ter ffmpeg
como uma opção de saída no Blender.
No terminal, verifique se está instalado ou não:
~$ ffmpeg
The program 'ffmpeg' is currently not installed. You can install it by typing:
sudo apt-get install ffmpeg
Quando você o instalou, verifique se ele está incluído na lista de formatos no blender:
Se não, você precisa fazer o download e reinstalar o blender. Por algum motivo, você tem uma versão que foi compilada sem ffmpeg
support. Você poderia experimentar uma das novas versões 2.49 RC.