I've seen the same thing on the iphone occasionally -- a song in itunes has artwork and on the phone -- just a black square. Causing it to re-sync can sometimes fix it (edit the song properties, maybe release date, in itunes, then connect up the ipod)....
