Я обнаружил, что отсутствующая зависимость находится в репозитории centOS, который в amazon ec2 не включен. Я добавил хранилище и смог настроить и установить ffmpeg. Для тех, кто делает то же самое, я рекомендую руководство Razuna, которое я упомянул в вопросе: http://wiki.razuna.com/display/ecp/FFMpeg+Installation+on+CentOS+and+RedHat
(Спасибо Rubberman на форумах Linux за решение)