As per the information pulled from this page: http://kubuntuforums.net/forums/index.php?topic=3109205.0, and a few modifications, vlc on Kubuntu 9.10 was playing 3gp video files in no time.
If you haven't already, add the Medibuntu Repo.
Run this line in the terminal:
sudo apt-get install libopencore-amrnb0 libamrnb3 amrnb ffmpeg vlc libavcodec-extra-52 libavdevice-extra-52 libavformat-extra-52 libavutil-extra-49 libpostproc-extra-51 libswscale-extra-0