I was having the same problem; album art in iTunes was correct, but on my iPod was all mixed up. Fortunately, I found this thread (thanks, people, for taking the time to report this and help us solve it!), and one of the solutions above worked--the one where you turn off sync for your iPod in iTunes, apply the change, then turn it back on, and apply again (resyncing your whole library to the iPod). Unfortunately, for 25GB of music, resynching your whole collection to correct a corrupted album art DB is a fairly TEDIOUS solution, but nevertheless, it solved the problem. Luckily, I've had this iPod for several years, and never had this problem until recently... or at least, maybe I never NOTICED it until now, because my new Altima shows album art when it's playing from the iPod (very cool). Hopefully it only HAPPENED recently, and doesn't happen again for another 4 or 5 years. If that's the case, this is a solution I can live with. If it starts happening more frequently than, say, every few months, however, you will start seeing angry posts from me on this forum/thread. 😐
Regards,
Maximillian in San Diego