MP4 video for mobile phone

[the_provider]

Greetings.

I am struggling to reach a method for converting .avi files to .mp4(mp4v + aac) that can be played on my Samsung Corby(S3650) mobile phone.
I have a video file that can be viewed and I tried ways (mencoder, Avidemux, HandBrake) to get a compatible one. I have several .mp4 files that according tu GSpot and MediaInfo look almost identical, except for "User/Meta Data"([USER] Lavc52.43.0 - for the NON-compatible file and
"©too:Lavf52.32.0
[USER] Lavc52.22.3") for compatible one. Also in MPUI's advanced info the playable video shows for FixedSampleDuration a value of 200 whereas for the NON- playable the value is 1000.
Following somebody's advice I used YAMB to demux and remux audio and video but again with no positive results, I can only hear audio but NO video can be seen.
All software used are at the last version/build.
There are a number of reasons why I would prefer to have something like mencoder doing the conversion such as hardcoding subtitles, have control over the proportions of the video, adding black lines, batch conversion, etc.
The playable file(2 MB) can be downloaded from HERE.

Being my first post I apologize If I posted in the wrong section.

Any help will be appreciated.

Best regards.