Well I just used VCDEasy and it asked me to convert to MPEG2, so I used WinAVI Video Converter to convert the AVI to MPEG2 then burnt it with VCDEasy and it worked perfectly. No sync problems at all.
I could probably use Nero now that I know to convert the videos to MPEG2, but I don't want to waste any more discs trying it >_<
I think I'll stick with WinAVI + VCDEasy for burning.
Oh, while we're at it, when I played the new VCD it was in widescreen format; with black bars at the top and bottom. Is that because of the settings I used? Do you know how I could make it 4:3? I chose those options in WinAVI but it didn't seem to do it.