Are you using iTunes 8? Do you get your album artwork from the iTunes store? Do you also have albums that artwork is not available from the store, but you have put on itunes yourself?
I have the same problem if you answered yes to the above. Apparently iTunes 8 does not readily show artwork that is stored in the song files metadata. Or at least, that is what i am guessing. I can highlight a song and the metadata artwork will appear, but not otherwise. It has really stuffed up coverflow and grid view for me, as well as not getting some artwork on the iPod.