I got this message today and ended up copy&pasting the note to a code editor (sublime text). There I noticed that it contained a strange Unicode symbol, obviously something that got copy&pasted from somewhere. After deleting the symbol and reinserting the note into evernote (had done it before deleting the symbol without success), the message disappeared, leading me to the assumption that evernote had problems with that Unicode symbol.
So in case you copy&paste something from somewhere and the note starts giving "note is invalid" messages, it just might be that some obscure symbol got pasted which evernote doesn't come to terms with.