I recently purchased a new phone, a Samsung S and I’ve been busily taking video clips as you do, only recently have I tried to stream them from my PS3 to my TV, only to find that the 3gp format isn’t supported under DNLA. After a little searching on-line, I’ve found out how to convert the file under linux, so I though I would share (as you do).
I’m having to make the assumption that you have ffmpeg installed, if not, then do so before following the instructions below.
Below show the info of the file that I’m converting.
The command line below seemed to work for me, thanks for linux.com for the more esoteric command line that worked best and produced the smallest file-size.
It’s always a good idea to make sure you get the aspect ratio correct “-aspect 3:2″ in my case, I would recommend reading the following.
ffmpeg -threads 2 -i video-2010-12-26-16-13-16.3gp -f avi -r 29.97 -vcodec libxvid -vtag XVID -s 720×480 -aspect 3:2 -maxrate 1800kb -b 1500kb -qmin 3 -qmax 5 -bufsize 4096 -mbd 2 -bf 2 -flags +4mv -trellis -aic -cmp 2 -subcmp 2 -g 300 -acodec libmp3lame -ar 48000 -ab 128kb -ac 2 video-2010-12-26-16-13-16.avi
Below are the details of the converted file.
Good luck 
References:
Article on parallaxed.net
HowTo install and use the latest ffmgeg (Ubuntu Forum)
FFMpeg website
howto-pages.org/ffmpeg
H.264/MPEG-4 AVC
catswhocode.com
Converting Audio and Video file using ffmpeg
FFmpeg Howto
