An easy procedure to convert *.avi files to *.mp4 (for example for use in Gallery) is described in this short article.

First, get the tool mencoder using apt-get:

sudo apt-get install mencoder

Next, use the find command to find all *.avi files in a folder (and its subfolders) and convert them to *.mp4:

find -mindepth 2 -type f -name "*.AVI" -print -exec mencoder {} -o {}.mp4 -oac mp3lame -ovc lavc -of mpeg ;
find -mindepth 2 -type f -name "*.avi" -print -exec mencoder {} -o {}.mp4 -oac mp3lame -ovc lavc -of mpeg ;
find -mindepth 2 -type f -name "*.MOV" -print -exec mencoder {} -o {}.mp4 -oac mp3lame -ovc lavc -of mpeg ;
find -mindepth 2 -type f -name "*.mov" -print -exec mencoder {} -o {}.mp4 -oac mp3lame -ovc lavc -of mpeg ;