Your iPod's album art databse is mucked up. Do this:
Mount your iPod in iTunes.
UNcheck "Show album art on iPod" and sync iPod.
Eject iPod, then dance a little jig*.
Mount iPod again, and REcheck "Show album art on iPod".
Sync iPod.
Your album art should be restored.
*Just seeing if you're paying attention.