What speed media are you using? Sometimes it is actually a good idea to burn faster rather then slower.
High speed drives and media were designed to be used at higher speeds. Try at 32x or so and see if that helps.
It could also be a low quality media issue. If you player is picky then you might want to try some different media (again try around 32x) and see if that resolves it.
You could also look up your DVD player in the DVD player compat. list found in my signature and see it there are any reports of issues with VCD's.