Just for grins, try using a different recording program, try buring a few files with windows xp's built in recording, or windows media player.
I realize they ****. Ok, they **** a whooole lot, but just try recording a file or two and see if they'll play.
Nero has so many crazy options, and standalone units (especially dvd players, but probably hu/mp3 players) are really anal about things, if everything's not strict iso standard format.