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 ;