iTunes holds its data in an XML structure. On the surface what may appear to you to be a single Album file consisting of 10 separate tracks may, in fact, be 10 separate tracks, each with a separate link to the Album artwork. How this comes about I am not sure, but I think it's related to how the files were input to iTunes. For example, ripping your own CD may produce a different result from 'acquiring' the same album from - shall we say, a download sharing site.

Normally what I do is

(1) if an album has no artwork, I select all the tracks and drag'n'drop the artwork (from Amazon for example) into the box for Selected Item. Normally this will lock the artwork to EVERY track in the album. If, however, the structure isn't 'correct' the artwork will only be locked to a single track. You can check by clicking on several tracks in the same album.

(2)If the artwork isn't there for all the tracks, you can select all the tracks, then go to File>Get Info and drop the artwork into the Artwork Box. You should then have artwork for every track

(3)Failing all this, as a last resort I drop the artwork in for each track separately.

One of these methods always works for me.

Bit tedious for a few albums, but for more than 1500 albums in my Library, I've only had to go the most tedious route a few times.

I should add that iTunes allows you to include several versions of the artwork for each track. If you replace artwork you may in fact simply be adding another version. Which one gets displayed is determined in the following way. Click a track. Go to File>Get Info>Artwork... here you will see all the versions of the artwork. Delete the ones you don't want. The one you are left with is the one that gets displayed.

I know.. it's confusing..

Here are a couple solutions for you:

A GUI Tool for Changing Genre Art

iTunes Genre Art Manager

From the website:

The number of genres recognized by iTunes and receiving an appropriate genre artwork is limited though. Here the iTunes Genre Art Manager comes into play. It allows you to add images to genres for which iTunes does not bring its own art. Also you can modify existing genre artwork to your preference.

The Manual Process for Changing Genre Art Images

Jochen Wolters wrote a detailed article on how to manually change the genre art in iTunes over at O'Reilly. There is also a Flickr group with alternate genre images if you don't want to go to the work of creating your own.