i believe i have a fix for some of those who have album art issues, namely, none of your artwork shows up on your iPod, but does show up in iTunes 7.x. i'm not sure exactly what models this will work for, but it worked for my 60GB iPod w/Color Screen, software v1.2.1.
my problem started when i tried fixing what seemed to be a minor glitch on the iPod-- some albums did not display artwork when playing from the iPod; yet, all art appeared in iTunes 7.1. i followed this hint on macosxhints.com that explained that if you uncheck the "display album art on this iPod" option, and then recheck it, iTunes will rebuild the artwork database and should rectify any album art problems. unfortunately, the hint didn't mention that on the iPod w/Color Screen, your artwork will no longer be diplayed AT ALL after you do this.
i tried restarting iTunes, resetting the iPod, deleting the ArtworkDB, resynching the iPod... nothing worked. i could see all the artwork in iTunes, it just wouldn't show up on the iPod no matter what i did.
fortunately, i received an email from the original author of this hint, and apparently he or she had the same problem that i had. when the hint was published, macosxhints.com decided to leave out the information that helped restore our artwork. anyway:
i'm not sure if this is limited only to the iPod w/Color Screen, but that's what i own and i did indeed seem to hose my album art on my iPod by following the above-mentioned hint. the fix is to connect your iPod to a mac that has an older version of iTunes (for both of us, this happened to be 4.7.1; i cannot vouch for any other versions). in iTunes' preferences, uncheck "display album artwork on your iPod", and then check it again. iTunes will then optimize the artwork (i've got about 4500 songs/22GB; this took roughly 15 minutes over firewire). when it's done, voila, your artwork is restored.
although it's probably a pain for a lot of folks to find a mac with a super old version of iTunes, this beats the **** outta moving your music onto another drive, reimporting, etc... also, all of your ratings and playlists will remain intact. i have no idea if this will work the same with a windows-formatted iPod, either, but it's certainly worth a shot, IMHO. good luck!