Several users have reported this over the years and it's usually the result of a corrupt artwork cache db on the iPod's hard disk. There are a few things you can do to try and correct this issue.
The first is to just try a hard reset of the iPod. To do this, press and hold both the Select and Menu buttons together long enough for the Apple logo to appear. A hard reset has no affect on the content that is stored on your iPod.
If no luck with that, try to un-sync and resync all of your content from your iPod via iTunes. To do this, simply remove the tick mark next to Sync Music at the top of your iPod's Music configuration tab in iTunes and apply the changes. Then reapply the option to resync all of your content back over to your iPod.
Try a restore of the iPod in iTunes. This process will wipe all data from the iPod and set it back to its original default settings. Here are instructions for restoring your iPod.
Restoring iPod to factory settings
Lastly, try replacing the artwork for the problem tracks with artwork that is of smaller size/resolution as larger size artwork has been known to cause corruption and other issues with playback.
B-rock