I was somewhat flabberghasted when I found out my mobile phone (Sony Ericsson Cyber-shot) was unable to play .mp4, .flv, .avi and what else I tried. It refuses to play all video formats save .3gp.
I was unable to convert to this with avidemux. Google quickly told me that ffmpeg could do the trick. But being unfamiliar with bitrates and stuff I was happy indeed when I found Mobile Media Converter, which is a neat and lean GUI for ffmpeg (Mac, Linux and Win). It even sports convenient batch process via drag & drop. Have fun.