I recently went through a huge ordeal trying to copy a VCD and so people don't have as many problems as I did here is a super mega happy guide.
I'm not sure if all this is needed but this is what I did:
This is the bit I'm unsure about for people; whether or not any more codecs need to be installed. I believe that I installed ffmpeg but I'm not sure if that was any help.
sudo apt-get install vcdimager cdrdao
The next section of this is to find something that can convert .avi to .mpeg,
the best thing that I have found for this purpose is avidemux:
Once that you have installed this open up your .avi file in it and then, on the menu bar at the top, click on the auto button and select VCD.
sudo apt-get install avidemux
This will do all the stuff that needs doing for it to work VCD style.
When this is eventually done you now need a program to actually write the VCD. The best one for this use that I found had to be k3b.
Once this is installed right-click on the blue section bottom middle and select make Video Disc. Now choose your file and burn the VCD.
sudo apt-get install k3b
I hope this has helped!
(P.S. I have only tried it on Gnome so I have no idea if it works on KDE or not)