I just spent over an hour on the phone with Apple Support (both L1 and L2 tech support). The L1 acknowledged that Apple has been experiencing server issues related to iTunes Match, and after going through some steps already outlined in this thread, the best thing to do would be to wait. After speaking to the L2 tech, he was less willing to own up to the problem, asking me to email the iTunes Store support team (who do not have a call center).
I did send off that email to iTunes Store support , but I also went ahead and tipped off all the major tech blogs about this iTunes Match issue. It seems that from experience, Apple tends to move when bad press begins to surface. If other folks here want to tip off the tech blogs too (along with calling Apple Support), I think that could go a long way to getting this issue resolved. Just go to the home pages of the tech blogs you read and look for a link that says "Send us a tip".