I've resolved my own issue and I thought I would post here just in case anyone else had this problem. Many of my mp3's had corrupt "headers" - it had nothing to do with DRM issues.
I don't really know what that means as far as the header being corrupted, but I guess an mp3 has a portion of the file called the header.
Anyway, winamp and my old archos 20GB jukebox WOULD play my corrupt mp3s just fine as the corrupt header didn't interrupt playback, but the Neuros and my PC's media player 10 would not. They simply refused to play the file at all.
My solution? I re-encoded all my mp3's to mp3 format using a program "Switch" and after doing so all mp3's played fine.
See link for program. I hope this helps someone else.
http://www.nch.com.au/index.html