I had also had no luck with the turning off/on iTunes Match. Frustrated, I went beyond these boards and found a couple of blogs that mentioned holding down the option key when you turn off ITM.( I also may have seen it on these boards from a frustrated commenter who was listing some of the things that Apple support suggested. Either way, I gave it a try.) Nowhere did I see any explanation about what holding the option key does or why I should do that. My guess is that it forces a rescan of your library since the first step, collecting information about your library, took much longer than usual. That used to be the only step that went quickly. Bottom line, I got through the whole matching process, but it took a long time. Walk away for 20 minutes and do something else. I am not even sure the option button trick is what did it since, in the recent past, I have gotten through, randomly.
One odd side effect: 3 songs that had previously been matched are now uploaded. Weird since these were "Matched AAC" songs that I had downloaded from the ITS. To me, this is proof that the matching process is flawed. Some of the exlanations on this board about why some songs do not match - how ITM uses waveforms and I must have a recording from a different master, just different enough that it does not match (eventhough it is from the same album) - well, this kind of blows away that explanation doesn't it?