Sounds like it should be a media issue, but it may be an issue with the reported BookType of the media you are using.
Some players on play DVD Media that have a BookType of DVD-ROM. These same players have trouble when a BookType reports as DVD-R, or DVD-RW, etc.
You can only change the BootType if your recorder suppors it of course.
To do this, simply put the DVD Disc you created in your DVD Recorder, launch Nero and go to the Disc Info window, and in the bottom left of the window, you will see an option for changing the booktype. This will only show up if your DVD Recorder supports it, and only if you have the Recordable DVD Media in the drive at the time.