I've had great success converting files to 3gp on Linux (or Mac) using the following ffmpeg settings. I creates a small file that plays back perfectly.
Code:
ffmpeg -i $SOURCE -f 3gp -vcodec h263 -b 400000 -s 352x288 -r 25 -acodec libfaac -ar 48000 -ab 96k -ac 1 -y $OUTPUT