I had the exact same problem with straight ffmpeg calls (about mpeg4) and couldn't get past it. I found this great linux app that will allow you to do that. It works on my Verizon LG9800. You can import the mpg files straight from /myth/tv and it will create your 3gp file.

http://www.kde-apps.org/content/show.php?content=35274

I installed this on my desktop ubuntu box. I haven't yet on my mythbox. Before you run it edit the install-ffmpeg file and add --enable-faac on the ./configure line. Be sure to go over the README file. Don't use aac or mp4, leave both unchecked.
I just started using it yesterday and haven't played around with any of the settings to increase quality, bitrate, size, etc. yet. Waiting for my sd card first.

##Update##
Received sd card so I did some playing with the settings. You can use the mpeg4 and aac toggles. I prefer them. mpeg4 is slightly better and aac is much louder.
3gp video, amr audio = vid qual=ok, sound = low
3gp video, aac audio = vid qual=ok, sound = loud
mp4 video, amr audio = vid qual = slightly better than 3gp, sound = low
mp4 video, aac audio = vid qual = slightly better than 3gp, sound = loud

I am going to use mp4 video, aac audio, set resolution to 320x240 and included the quality improvements from the comments section. Now video is very good, audio is loud and size is better because it is bigger.
2 hour movie straight from the mythtv .mpg file shrinks to about 150 meg. Lots of room on 1 gig mini SD card

_________________
ASUS A7N266 Micro-ATX Motherboard
Athlon 2200 processor
512K Kingston PC2100 Memory
MicroAtx Case
2 PVR250's w/remote
eVGA e-GeForce mx4000 (64 Ram with Tv/Out (Svideo))
Lite-on DVD cd-rw combo
120 GB Western Digital