Nokia Multimedia Convertor will do the job. It's free but needs a registration at the Nokia Developer Forums (free too) before downloading.
*www.forum.nokia.com/main/0,,034-63,00.html
For better quality and more control on bitrate try this free tool
*www.videohelp.com/tools?tool=3GP_Converter
Here's a guide for PSP - *peripherals.engadget.com/entry/1234000980024404/ - but you can adapt it for use on your phone by lowering the video res to 208x176 and a video bitrate of <160kbps and audio < 20kbps, <22khz.
-Keith