i had lots of problems shoving movies on my ipod. seems like i found the recipe. also works for samsung omnia. with ffmpeg.

ffmpeg \
  -i "input.avi" \
  -b "768k" \
  -s "400x226" \
  -vcodec libxvid \
  -r 25 \
  -ab "128k" \
  -acodec libfaac \
  -ac 2 \
  -ab "64k" \
  -f mp4 \
  -y "output.mp4"