Hola everyone.
I got myself an interesting project this morning again...
I was trying to do it for a while but never had a time or patience to do it from A to Z...
I have a Nokia N73 dumbphone... Its not very smart but it does what I need most of the time.
Sometimes ago I had similar project - a friend with a PSP and family videos. It took me a while then and I have decided that one day I will convert my stuff to play on my Nokia too

.
I was trying several times / different methods and finally found solution that satisfied my needs.
1) Open console
2) Use command:
mencoder -of lavf -lavfopts format=mp4 -oac lavc -ovc lavc -lavcopts aglobal=1:vglobal=1:acodec=libfaac:abitrate=128:vcodec=mpeg4:keyint=25 -ofps 25 -af lavcresample=44100 -vf harddup,scale=320:-3 -mc 0 -noskip /path/to/the/input/file.avi -o /path/to/the/output/file.mp4
3) When the conversion is all done connect Nokia via Bluetooth or with a USB cable
4) Open Nokia's storage via file manager ie. Dolphin
5) Find folder Videos (should be in the main folder of the card if not create it)
6) Paste the file.mp4 to the folder
7) Safely remove the device
After that You should be able to watch video on Your Nokia.
I am sure that converting any other (then avi) input file is a go...
Hope this helps.
Andy