Album art has always been a pain, but I've found that if you edit the album art embedded in the ID3 tag so that it's no more than 500x500 pixels and less than about 50kb, then most times it'll work well after a re-index. I just added music to my Zune HD yesterday, and with the original album art (800x800) from the Zune marketplace, I got the same Gracenote placeholders. Exchanging them with the smaller 500x500 (or less) files generated better results.
I used MP3Tag to modify the tags. It'll find new art for you from Amazon and save it to tags, but you have to do it manually for each album. Musicbrainz Picard might do it automatically for your whole collection, but I don't know for sure. I do know that Ford had "Sync my iTunes" as well, but have no experience with that.