This may be a long shot but try this, first back up all your songs to your PC and then open up your app manager (from your home screen Menu button -> Manage apps). make sure you have the ALL tab selected in the apps management and scroll down to "My Music" and select that. In there, press the "Clear data" button. This will not delete your music instead it will wipe out the Cache (like your most recently listed to songs and such) and wipe out the database of the music app which holds ratings you may have done and album art.
You'll need to let it rebuild the database again to pull in all the album cover art but I think this may fix your problem, worth a try.