I have had issues with album art on my 3rd gen. iPod Touch since the update prior to iOS 5. The wrong album art was displayed for most podcasts and in most cases, the album art was scrambled. The iPod-generated album art for Genius Playlists would often appear instead of the correct album art for many podcasts and in playlists of videos.
When the restore from backup failed after updating to iOS 5, I did a fresh sync of selected playlists to the iPod and many albums had similar issues of displaying the wrong album art and sometimes displaying it scrambled.
I am not an expert on programming or hardware but I suspect there is some fault with the 64 GB SSD in my iPod, or the memory module because if it was simply a software fault, the latest update would have fixed it. If this is confirmed to be true, it will be a disappointment because I upgraded from a hard-disk based iPod thinking the non-mechanical iPod Touch would be more reliable.
I know business realities dictate that Apple should encourage repeat sales of bigger and better iPods but I wish I could buy something that could last longer than 3 years without making an upgrade necessary.