The problem might have to do with Nero which isn't very good at encoding Mpeg videos. I suggest you convert your AVI files to MPG files first using other "good" software. Then you can use Nero to write the Mpeg videos directly onto a VCD.
Many NLE software such as Premiere 6.5 are pretty good converting AVI to MPG format. But those software are expensive and take up lots of your system's resources. In other words, they are s-l-o-w in converting videos.
I recommend a free software called TMPGenc which I'm using now for making Mpeg1 videos. The pro version (which extends the conversion capability to Mpeg2) is not free though. Here is their official site: