Use ffmpeg for audio/video transcoding. It supports about every format known, and many not-so-known. For complex tasks it isn't easy to use, but for simple transcoding tasks it isn't difficult to use (in my opinion). It is quite simply awesome in its capability, and is used by a lot of other tools (both CLI and GUI) under the covers for audio/video conversion tasks.
As it stands right now the version of ffmpeg in the repositories doesn't have support compiled in for the standard audio streams in 3gp files. You will be able to decode the video stream, but not the audio and completely unable to encode the audio out....... This limitation extends to all applications which use ffmpeg in ubuntu right now for conversion (Including winff, avidemux etc.) Handbrake will work right now because they have their own custom compiled version of ffmpeg included which has support for these formats compiled in. Also barring ffmpeg as the backend, mencoder works just fine handling these files so any frontend which uses mencoder as the backend will work just fine.
I believe that this issue is only pertinent to Ubuntu and derivatives at the moment, and a custom compilation of ffmpeg will correct the issue.