That comes up if the song can't be found - are you sure you can play it? It shouod have an ! beside the title signifying a problem.
If not, then that's the first I've ever came across this irregularity.
If you select the song, Get Info (Command I) then see if you can navigate the tabs in the panel displayed to Artwork or Info - if you've already copied the Artwork image, then in Info, you should be able to select the Artwork field, highlight it, and paste.
If you've the image on the DT/in a folder, then the Artwork tab should allow you to Add it.

If not, then remove the entry in Library playlist, find the song in the folder where it's stored, and drag and drop it onto iTunes again to add it again. Other than that - the song itself must be corrupt somehow. Re-import it again from the CD in case there was a problem with the encoding process first time round.

Can I ask if this is a "legal" file? If so, then re-import it again from the CD.
If not, then whatever encoder was used or machine, has done something that has locked out the album cover ability.
I take it it's an mp3 and not WAV or anything else.

Ah..of course, completely forgot about that as a possibility (shows how often I've ever used it!). Here's hoping that's all it is.

check ownership & permissions on the file in your iTunes Library - I had that a few times and the ownerships were set to read only. That was only with files I importet myself, though.

I found your question looking to the answer to the same question. I couldn't figure out how to change ID3 tags, permissions, read-only settings, etc. and get it to work. But the reason that I had the problem was that I was using Fetch Art to get the album artwork ... long story short, instead of doing a copy, paste like I started out doing, I just selected all the songs I wanted to add art to and used Fetch Art again. Worked like a charm and no errors. No idea why it will work when no other method does, but who cares!

If you don't have Fetch Art, you can get at http://staff.washington.edu/yoel/fetchart/. Great little app/AppleScript!!!