Software patents led Debian/Ubuntu to disable the H.264 and AAC encoders in ffmpeg. See /usr/share/doc/ffmpeg/README.Debian.gz.
So go install x264, mplayer/mencoder, and Nero's AAC encoder. (Or, if you want to use all Free software, and don't care so much about audio quality, then sudo aptitude install faac.)
I don't remember if the medibuntu package of mencoder includes x264 vid encoding, since I build my own from git x264 and svn mplayer sources. (x264 is very actively developed, with significant quality and speed improvements frequently added.) http://git.videolan.org/?p=x264.git;a=summary
x264 is also packaged, but you should check that it's up to date enough to include weightp with recent bugfixes, and even more recent speed improvements...
Or if you're already willing to convert from .flv, instead of going from the high-quality source the flv was made from, then probably whatever recent version of x264 you can find will be fine.