Download the free/trial version of TMPGEnc and use the free DivX codec. XviD will provide better compression, but isn't quite as intuitive. Just install DivX or XviD first, then launch TMPGEnc. It makes it pretty idiot proof. No, I'm not calling you an idiot.
You probably have to transcode it back to MPEG 1 or 2, then AutoGK it again. Probably the same with the programs like TMPGEnc that people are using to make PSP compatible MPEG 4s.