iTunes artwork doesn't change
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..