How can I convert .mp4 files to .3gp using ffmpeg?

Use the following command:

ffmpeg  -y -i movie.mp4 \
        -r 20 -s 352x288 -vb 400k \
        -acodec aac -strict experimental -ac 1 -ar 8000 -ab 24k \
        movie.3gp

You probably just need to install the non free/restricted packages of ffmpeg like libavcodec-extra-53 libavformat-extra-53 libavutil-extra-51 and the likes.

Calling ffmpeg with --list-encoders will show the available encoders.

You are doing everything right :). You will have to install for the conversion to work.

Ubuntu Restricted Extras, i.e. libavcodec-extra-53

You may get it from the software center or use the following command

sudo apt-get install ffmpeg libavcodec-unstripped-52

I ran into problems with ffmpeg too

Apparently, ubuntu is no longer using ffmpeg, but a fork called avconv. This makes some (many ?) commands found on sites unusable on ubuntu.

What I did was just get the original ffmpeg:

sudo add-apt-repository ppa:jon-severinsson/ffmpeg
sudo apt-get update
sudo apt-get install ffmpeg

not sure how much this would help you, though