VLC does not play all VCDs in Linux. You can play VCDs using Mplayer instead. Open a terminal window in Linux and type the following command to do so:
$ mplayer vcd:://4 -cdrom-device /dev/sr0 <enter>
If you notice the //4, that is the track on the VCD. Change it if the VCD does not play with 4. Try any other numbers starting from 0. In my case, the CD ROM device is /dev/sr0.