That does sound like it may be an issue with the burning, or perhaps the bit rate.
Are you burning at the slowest possible speed? Higher speeds are more prone to error, so use the lowest speed possible. What brand of media are you using?
Regarding bit rates, most DVD players have problems with higher bit rates on burned DVDs (this is not a problem with replicated, aka “stamped” DVDs). If you are using Automatic Transcoding (i.e., you are not applying any transcoding settings in Encore), then make sure your project setting is 7 MBps. If it was higher, then you’ll have to revert your media to untranscoded and re-transcode it. If you are using a custom setting, make sure the maximum doesn’t go over 7 MBps (or not very much over that, anyway).
One or both of these may be contributing to the problems you are seeing.