I actually figured out what is causing my 4010 error, but not why it's causing the error.
Since I could select individual files and choose "add to iCloud", I decided to try selecting more and more of them and see what happens. Eventually I got the error. At that point, I managed to pinpoint the problem down to a single song. What's odd is that song is already "uploaded" to iCloud.
When I removed that song from my iTunes library, but not from iCloud, I could update iTunes Match. Thinking something was odd with that song, I removed it from iCloud, changed it's name and put it back in my library. At that point the 4010 error returned when trying to update iTunes Match, yet I could still right click the song itself and choose "add to iCloud" and that worked.
So there's something about having that song on my drive (in my local library) that causes the Apple iTunes Match server to freak out when updating, but has no problem with it when uploading it individually. Very odd.
Edit:
I edited the MP3 tag to remove a comment, add an artist name and a track number. I then added it back to iTunes and now it works. Very, very odd since it used to work before.