Usually if it doesn't play... It's not gonna.
a) Looking up the DVD Player at VideoHelp.com and seeing if anyone has gotten VCDs to play. When a player says Video CD, it could mean a factory pressed one, it doesn't have to mean a burnt one.
b) Try CD-RW media. My old Panasonic would only play VCDs off a CD-RW.