I guess .3gp is the proper extension, it appears that's MPEG-4 of some sort, but for whatever reason the MPEG-4 files I have don't work. Is there and good, easy to use software to transcode into something usable on my phone?
I use Subsonic for audio and video playback on my phone, never had any problems. The great part is that it's all streaming - you never need to upload any crap to your phone to make it available. It just... works.
Super easy to set up if you're at all technical.
http://www.subsonic.org/pages/index.jsp
Edit: If this is not what you're looking for, I've heard that Handbrake's "iPhone" setting should convert to a playable format on most Android phones. Never tried it though.
Have you tried playing it with Rockplayer or VitalPlayer for Android? I believe both can play 3gp files.
If not, you can convert using Handbrake on PC. But try the above programs first.
Sorry, I think there's some confusion. I have MP4's (avi format) that I want to play on my phone, and thus need to transcode them to .3gp format.
Rockplayer (free on Android Market) will play .avi's without needing to convert them. Plays my avi and divx files fine, should work with what you're trying to do. Worth a shot though.