Deleting your iTunes Match library is not neccesary. I had this exact same problem last weekend. I only just subscribed to Match about 10 days ago, so last weekend I was TRYING to upload all my stuff to their cloud, and kept getting the 4010 errors. After a while it got so it didn't even get that far, and I just got an 'service unavailable' type of message. The only reason I'm not getting the error today is that I'm not about to go through THAT again, and I have no need to update my library right now. I feel your pain, and it is very frustrating.
AFTER Apple fixes the problem (last weekend it was fixed by Monday), you WILL need to turn off Match under the Store menu and then turn it back on and relog into it. IFF the service is working, it will then go through steps 1 & 2 over again, and then step 3 should pick up wherever you left off. The process of uploading a lot of unmatched tracks takes a long time, so you really don't want to have to start that all over again.
I talked to a tech last week and he thought the problem might have to do with Apple's phasing out the Me cloud and moving everyone with Me over to iCloud.
For whatever it's worth, I also had to turn off 'QoS' in my DSL router before I could get a stable connection even when everything was working on Apple's end. I have no idea why this would be.