That's what I did with my iPad and it fixed it, so worth a try.Im having album artwork problems on 5.0 eric, lots of them are not showing. I'm going to try a re-sync to see if that fixes it.
Not the same problem I know, but I suggest you try the same thing.
I done that and it changed and worked right only after i restored my iPhone for many other reasons!the best way to fix the artwork issue is to remove all the music from your phone/ipod/ipad, make sure all the artwork in your iTunes is correct and you only have one image for each album, then resync the music back to your device. That, in theory, should do the trick.