So what are the source files? .avi is a wrapper format that can contain just about anything- MPEG1, MPEG2, DivX, Xvid, etc.
If the source is an MPEG 4 variant, it is quite possible that the fault lies not with Nero, but with the codec you are using (or some combination of the two). The next step would be to figure out how it is being decoded. Xvid, ffdshow, etc. can all decode multiple versions of MPEG 4- often in their own quirky ways that may not be completely compliant.
Create a control by reencoding to DVD compliant MPEG2 using virtualdub or some other video manipulation program. Problems with that file would point to a source file/codec issue while a clean reencoding would point to a Nero incompatibility.