Have you put the video on your computer? On your computer you should try to put it on the highest possible resolution, but if you're going to use the computer to put it onto a VCD, a small format of 640x480 will be fine.
This is because a computer monitor has much more pixels than a TV and something which appears to have crisp quality on a 28" TV may not appear good on a 15" monitor. Are you enlarging the video by any chance? Try to view the video in 100%, enlarging it too much will make it have large pixels.