Hopefully this will help someone else.
I wanted to post this to try to help other people out there who are frustrated with the Album Art and other iTunes issues. This information builds on things I learned in past iTunes versions, but this is mostly about iTunes 10.5.1, and iOS 5.0.1. I ran in to all these problems after I updated iTunes and the iPod, and a BIG mistake I made is I have not been keeping up with backing up iTunes. I had three problems, I was missing songs, I was missing album art, and I had a problem with one of my apps I just updated. I had to find a way to find an earlier version of that app, Snaplink Mobile, and then revert to back to it. But that's another issue that doesn't affect most people, so back to the music issues. I'm not saying this will fix everyone's situations, but this will probably work for most of us. I read all the posts from people who lost all their album art. I had to do the below and 2-3 syncs before I saw most of my art back.
First, I had to find a way to get ALL the music off of both iTunes and the iPod. I can't emphasize enough what a mistake it is to reset the iPod or iTunes to factory settings before you try everything else! There were 3 videos I brought that only existed on the iPod after I reset iTunes, and if I had reset both the iPod and iTunes before thinking, I would have lost them. So, what happened was, it is not that clear in iTunes 10.5, you have to go to the iPod tab, then the music tab, and uncheck the box that says "sync music", then at the bottom hit apply. This does not erase your music, it just removes it from iTunes. Then on the iPod, version 5.0.1, I had to go to Settings, then General, then Usage, then Music, and then there's a hidden delete button for the music. Under "all music," sweep your finger across the right side of the all music bar, and the hidden delete button will appear.
Then, it took 2-3 sync's to finally get both the iPod and the iTunes with no music. Then, I re-checked "sync music" on iTunes and on sync, all my music was back on the iPod. Then on iTunes, I clicked "consolidate library" and it copies (it does not move) all your music in to the iTunes music folder in one place. Now all my music was back, but still a lot of art issues, so on to that.
If you use Google Images, you can find a LOT of missing album art, a lot of it is on Amazon, and other sources. You want images that are square, and somewhere between 300 x 300 and 500 x 500, ideally. Then, I use Microsoft Paint sometimes to edit the album covers if I want to change something small about the way they appear. Then put all the art in a folder in the same place. Of course, you can also run "find artwork" in iTunes to find most of your stuff.
Now, a key thing to know is in the iPod, the album cover you see is pulled from track 1 of that music! If the album art you see in iTunes is being pulled from a different track in the album, it will NOT appear in the iPod in your album list. Databases are funny things, you have to know exactly what you're doing to work on them! So, what you need to do is figure out where the album art you want for an album is at. Use "get info", and find the album art you want for an album, and then right click and "copy" it. Or, bring it up in Microsoft Paint, hit select all, and hit "copy." Once you have that image, you want to make sure it is loaded for ALL tracks in that album in iTUnes. As many have said, doing one track at a time, using "get info" is maddening and time consuming! Fortunately, there are some shortcuts! Once you have the album cover copied, there are several methods that work to get it on the entire album, all tracks. One is, to type in the search bar on iTunes until only the album you want to work on is showing on the screen. Then you can use "select all" to highlight all the tracks in the album at the same time. I had a few instances where this method alone would not bring up just the one album, so select all will not help in that case. But fortunately, you can go through all the tracks on the album you want to work on, holding the "control" button down on the keyboard while you click multiple tracks. This allows you to select manually more than one track. Now, right click on all the highlighted tracks and hit "get info." In the box that comes up, go to where the album cover is and right click and select "paste." NOTE: You will see the check box next to the album cover come on with a check, but you will NOT see the album cover you just pasted until after you apply this. When you hit apply, you will get a message that says "do you want to edit multiple items at once?" Say yes. It will then load the right album cover for all the tracks in the album, and fix a LOT of problems you're having.
Another thing you may have to do for some or all of your albums is on the same right click menu that "get info" is in, there's another one "view in windows explorer." You may have to select all the tracks using select all, hit properties, and make sure the files are NOT set to "read only." That causes a lot of problems too. It's also possible to right click on your music folder, and make sure all files and folders are not set to read only, but all at the same time.
So, it would be SO great if Apple would be better at getting this type of information out in a clear an complete fashion, but that does not seem to happen.
And, always back up your iTunes!
Lee