I think iTunes Match has been a disappointment. Has anybody had trouble getting it to display artwork? I'm missing artwork for 10% of my library and deleting it from the cloud and rematching it doesn't seem to help.
I'd the same issue early on when it launched, but after updating the artwork one day, it all just ended up pulling it.
Try updating the artwork on the tracks and updating iTunes Match. After you're done, turn off Match on the affected device and make sure all of your music is gone. Once you've confirmed that, turn it back on and let it do its thing.