The artwork database has been know to become corrupted across all models iPods. As to why there is no for sure answer, but could be the resulted of corrupted artwork images, failed sync operations with iTunes, are the artwork database just being to large for the iPod to work with even though it was designed to hold much larger music libraries.
Sometimes a simple reset helps. To do this, press and hold both the Select/Center and Menu buttons together long enough for the Apple logo to appear.
If no luck there, remove and resync all of your music via iTunes. Sure this is long and tedious, but it's really only one of the few remaining options.
Lastly, restore the iPod to factory settings and resync all content back over to it.