Wiping cache didn't help.
This is so weird. Read.
When I copy the song with the messed up art to PC, it has the art embedded, but it doesn't show it. However, when I switch to Large Icons view mode, the art shows. Then, if I go back to Medium Icons, it shows it.
I suppose the problem above is due to the Windows Thumbnail cache. But... why the device? Why is it not showing the art correctly? And what criteria is it using in choosing the random art that it does show in place of the correct art?