Others have posted solutions, and I thought I'd share what's worked for me, similar to solutions that have been posted in this thread. This method requires having iTunes Match on two separate computers. I might add that one of the maddening parts of this is that changes to metadata do seem to propogate through iTunes match, but not changes to the artwork.
The gist of this method is that you have to remove the album from iCloud, change the artwork, and then upload it back to iCloud to make the changes stick.
I have iTunes on three computers (shared through match): A main family Mac Pro at home, a Macbook Pro at home, and a work PC. I use the Mac Pro as the "main" computer for this purpose. Obviously, make sure Match is updated on the computers you are using. I generally do all this in Album View on iTunes.
1. On the "main" computer, delete the album you wish to change (I usually find the album in Album View, select all the songs on the album, and press delete). Check the box to delete the songs from iCloud as well, and send the files to the trash can.
2. On the other computer, select the album (which should have the little "x" symbol next to the songs indicating that they are no longer on the cloud - if they don't then you may not have deleted them in step 1 above). Select all the songs on the album, choose "Get Info", check the box next to the artwork on the metadata page (under the tab "Info"), click in the artwork box and press "Delete" on your keyboard (not sure if this last step is necessary), and then click "Okay." If you are in album view, the artwork for the album should disappear.
3. Go find your new album artwork. I use Google, and set it to look for 500x500 sized images, but obviously your preferences may vary. Once you find the artwork, simply right-click on it and "Copy" (or command-C). Make sure you're clicking on the actual image you won't, not a preview-sized image. There doesn't seem to be a need to save the image locally.
4. Go back to iTunes, and again select the songs on the album you're working on. Choose "Get Info" again, and click on the artwork box and Paste (command-V). Once it's done, you should see your artwork appear; click on another album and then back on the one you're working on if you need to double-check.
5. Finally, once again select all the songs on the album. Right-click on them and choose "Upload to iCloud." iTunes should then start updating Match.
6. Once it has finished updating, the album should be available in iCloud, and you can go to your main computer and redownload it.
One note for step 5, if you do multiple albums at one sitting, the update process doesn't seem to work right. When the iTunes Match update process ends, it will likely have only uploaded the first album you did. Once I finish a session, I'll stop the updating process (click the little "x" in the status box at the top right next to where it says "updating iTunes Match information" or somesuch). Then go to the "Store" menu, and choose "Update iTunes Match." Everything you've already flagged for uploading then should upload properly.
Hope this helps. It's a pain, but it actually goes pretty quickly, and I find it pretty easy to do on my Macbook while watching TV.