1. Раскидываем gif-ку на кучку отдельных изображений:
convert исходный_файл.gif gif%05d.png
2. Собираем из изображений видеофайл:
avconv -i gif%05d.png результат.flv
P.S. Вообще-то в сети полно решений с использованием ffmpeg, но в штатных репозиториях своей Ubuntu 14.10 (Utopic Unicorn) я эту штуку не нашел.
