It already can do this. 3gp IS MP4 (mp4 video, and mp4 audio). I just tried it with my Borat DVD (get it earlier because of where i work. Worth buying, pretty funny. I just converted a bonus video clip, and my Samsung A920 played it just fine. You just tweak the setting is all. I will in the near future actually make a preset and post it. Maybe the authors might include it.
Right now i used the 176x120 (16x9 video clip is why) and 256 Bitrate, 14.98Fps (looks just fine on a small screen. You wouldn't think so in the days of Doom1 on a 486, unplayable!!), 64kbs Audio, 1pass (2 pass isn't ever needed for this size. Could help, but tried it, couldn't see any difference to the naked eye.)

I will mess with this more later and tweek the best settings for lowest filesize vs. best retained quality. I already have a tweaked setting i use to convert my Simpsons, and Family Guy episodes using 'Xilisoft's Video Convertor 3', but it looks like this will work just as good now instead, now that Preset making is possible. You don't even have to change the file extention. It's recognized anyway!!!

UPDATE!!-
I quick threw together something before leaving, since it was pretty quick to do- copy and past into a text file, and rename it to 'generic.cellphone.mp4.aac.xml'

<profile name="generic.cellphone.mp4.aac" version="200" device="generic" tag="dvdfab,cellphone" description="The profile is used to create mp4(mpeg4 + aac) file, which can be played on Cellphone's.">
<common>
<file format="cellphone" mode="0" onefile_size_mb="512" number="1"/>
<audio codec="aac" channel="2" >
<freq value="24000" list="24000,32000,48000,64000" />
<bitrate value="24000" list="24000,32000,48000,64000" />
<volume percent="120" />
</audio>
<video>
<size list="176x120,176x144,240x176" />
<outfps mode="3" value="14.985" list="14.985" />
<encode codec="mpeg4" bitrate_kbps="512" maxbitrate_kbps="1024" >
<mode value="real_time" list="real_time, high_quality" />
</encode>
</video>
</common>
<acodec name="faac">
<common profile="1" quality="100" />
</acodec>
<vcodec name="mpeg4">
</vcodec>
</profile>


Maybe someone else here can help with getting things to show a separate "Mobile Phones" to show in the left side list along with Generic/Psp/iPod, that was i can further tweak it to have this as one profile under that. I don't personally know how, but probably could later by using that 1 user who did this already but for the Creative MP3 player, might take a look at that later when i get some time. Enjoy!!!