Hi guys,
Not sure how many people have solved this problem since this thread started, but since it's something I've both encountered and solved recently, I thought I'd chip in.
Like many others, I had a full library of music with artwork on every single track with some tracks refusing to show artwork on my iPhone 5S when iTunes Match was turned on. I also knew that it wasn't a picture format issue, because some songs in an album would display the artwork and some wouldn't (a popular trend was seeing the first song with artwork and the rest of the album blank).
I was about use a solution someone posted here which involved deleting the individual songs from both iCloud and my library and re-adding them, but I tried something else instead which happened to work.
-Select album view on iTunes
-Find the album which has songs with missing artwork
-Right click the album and select 'Get Info'
-Clear the album artwork (this can be achieved by checking the box 'artwork'), then click OK
-All songs in the album should now have no artwork
-Right click the album and select 'Get Info' again
-This time, copy and paste your album art into 'artwork' (this will automatically check the box), then click OK
-All songs in the album should now have artwork
-Check Music on your iOS device and scroll through your songs allowing a few seconds for missing artwork to load--it should now be there.
I don't know exactly how this worked, but removing all artwork from an album and re-adding it appeared to refresh the cache, so iTunes Match now recognises the songs as having album art again.
Another trend I noticed was that individual songs that didn't have album art on my iPhone had the artwork tab missing when I clicked on Get Info in iTunes. However, adding all the artwork back to the albums themselves brought this tab back for individual songs, and subsequently they showed up on my iPhone.
Hope this helps someone.