This is easy. you've just got a corrupt art database on your iPod.
Do this:
Mount your iPod in iTunes. On the summary page, UNcheck "Put album art on iPod".
Sync iPod.
Eject iPod.
Put your left foot in, take your left foot out.
Shake it all about (your foot not your iPod).
Mount your iPod in iTunes again.
This time REcheck "add artwork".
Sync.
All your art will be re-copied to the iPod correctly.