Скорее всего, не тот кодек выбрали, ну итд в настройках вашего энкодера. Вообще, mp4 контейнер с Н.264 видеопотоком должен переупаковаться в flv вообще без перекодирования, будет только смена контейнера(т.е.почти мгновенно, если нет-то либо вы напутали, либо Медиа Енкодерор вообще кривой)
Попробуйте вот этим переделать из мп4 в флв
http://www.erightsoft.com/SUPER.html
не справитесь - скинете мне файл, я вам его в флв сделаю с тем же качеством.