It does sound like it might be a pure readability problem, in which case using a different make of DVD blanks would certainly be worth trying.

However, just to be on the safe side and rule out that this is not an issue caused in the DVD encoding and authoring, you should also check in the MPEG encoder settings (within the burning dialog) that you're creating the correct video standard for your country (NTSC/PAL). NTSC would be the right choice for e.g. North America and Japan. PAL would be the right choice for e.g. Europe and Australia. I suppose, if you're actually authoring something other than a standard video DVD or if there is indeed a problem with the video standard setting, you might get confusing results, as the medium could possibly be processed by some devices and not by others. However, if there's no doubt about the fact that a proper DVD with the right video standard was created, it boils down to readability issues. Ironically, it seems to be a common experience that some brand name players will fail to read certain home-made media, while affordable no-name alternatives will eat literally anything you throw at them.