Is the problem also there when played on the PC?
What software are you using to encode and to burn?
http://www.dvdrhelp.com/vcd - Try downloading and burning a pre-prepared VCD image, to see if the problem is in the burn, or in the formatting of the audio.
If that "canned" VCD doesn't work right, then nothing will - if your player can handle CD-RW media, it may be worth using a CD-RW until you find what's wrong.
If it's still playing the video, it can't be having any significant problem reading - at least, you'd expect to see the video disrupted in some way, surely?