What brand of media are you using? Have you tried a different brand and gotten the same results? You could try reducing the burn speed (for example if the default is 8x then you could try 4x) to see if that helps. Are you using DVD +R or DVD -R? With some players this will make a difference as well.