OK, I think I have some big help here.. it certainly made my life easier. I can't stop it from happening but when it does, this fix is massively better than deleting all your music and re-importing. Took me about 5 minutes to fix/sync for 20,000 songs.
Just simply delete everything inside your album artwork cache folder. ~Users/username/Music/iTunes/Album Artwork/Cache/
It forces the iPhone to relink all the correct album art from your iTunes app to your phone.
Important step: After deleting the cache, open iTunes and view in Album View. Then scroll through all your albums, which forces the art back into the cache. I'd go up and down a few times to make sure they're all back.
Then sync your iPhone. You'll see the added step where iTunes is copying over all your album art. Everything should now be back to the way it was.