The default install of ffmpeg on Ubuntu Dapper does not come with support for encoding mp3. I had to get the source and re-compile with mp3 support using lame as the encoder.
Make sure you have multiverse and universe enabled.
$ sudo apt-get build-dep ffmpeg
$ sudo apt-get install liblame-dev libfaad2-dev libfaac-dev libxvidcore4-dev liba52-0.7.4 liba52-0.7.4-dev libx264-dev
$ apt-get source ffmpeg
$ cd ffmpeg-*/
$ ./configure --enable-gpl --enable-pp --enable-pthreads \
--enable-libogg --enable-a52 --enable-dts \
--enable-dc1394 --enable-libgsm --disable-debug --enable-mp3lame \
--enable-faad --enable-faac --enable-xvid --enable-x264
$ make
$ sudo make install