This sounds like a media compatibility problem after all. The NEC ND2500a is known for it's poor reading capabilities. It's a very good burner, though an almost worthless reader.
Depending of the version XBOX you have, you might be suffering from the same prob. There are three different versions of XBOX DVD drives: Philips, Samsung and Thomson. They all have their problems with certain media.
You could try to burn discs at the slowest speed possible, Sometimes this gives better results on XBOXes.
Can you perhaps post some more info on the media you used, together with the firmware and maybe other important settings?