If ViewNX is saying that then I would conclude the internal structure is corrupt. As NEF is proprietary I don't think there's a publisied file structure like JPEG, TIFF etc. But I would assume it is the same logical structure that would start with a header encoding and the location of the JPEG (thumbnail).
I had a look over on Nikonians.org and theres a few posts but nothing like what you describe with the in camera red X.
I would suggest taking a disk image of the card on the Mac just in case you do something more to the card.
If you want to send me a file I can try it on my iMac too, I'll PM you my e-mail.