Muchas de las herramientas de edición de vídeo para Linux se basan en FFmpeg para la conversión entre formatos de vídeo. La versión que viene por defecto en los repositorios de Ubuntu no tiene soporte para x264, así que si queremos trabajar con este formato, una buena solución es compilar este programa desde el código fuente. También hay por ahí repositorios con una versión con soporte precompilada, pero esta solución me gusta más.
Además, los pasos que hay que seguir son realmente sencillos y de regalo siguiendo estos pasos también se instala el soporte para Theora para FFmpeg, que ya viene en su última versión en los repositorios de Ubuntu 10.04.