I think I figured out a fix. You basically need to redo the album art for the albums that are not working. I don't know if this was related to the fact that the albums with the problem had 600x600 album art or what but this is what I did.
1. Get the album art file, you can export it from the album by opening "info" on one of the tracks, then under the artwork tab, drag out the image to your Desktop (or Finder).
2. Open the image in an editor, resize image to 500 pixel max, save a PNG (that's what I did at least)
3. Select all tracks in the album, open "get info" on them and click the checkbox on album art, then click okay, removing the existing album art.
4. Repeat step 3 but instead drag your new image into the album art box.
5. Repeat the above steps for all the albums that have the issue.
When complete, go to "Store -> Update iTunes Match" and let it go through the update process.
Now you are done, your albums will update on your iDevices. You might need to restart your iDevice before it will see the changes, also sometimes you also need to play a track from the updated album.
Note that I am not exactly sure what part of the steps fixed it for me, but doing a straight "Update iTunes Match" did not fix it for me, until I went through and fixed each album's artwork.
Also you might not need to restart your iDevice after, but it seems to help force the update because it might not always check for updates all the time.