Attention: GMCC58 - I did what you said. I turned off iTunes Music Match, turned it back on and it reacted differently.
It ran past step one, got hung up on step two for about 30 minutes.
I wasn't looking when it finished, but it did run through completey - it said "your music is now in iCloud.
To put it to the test, I deleted a song from my library, not from the cloud and moved it to the trash.
It placed a cloud symbol next to the song. I double clicked on the song and it download and restored the song.
I guess, you have to keep turning it off and back on and keep trying.
Ive had this service for almost a year. It never reacted like this. The whole process would only take a few minutes (after the initial music match which took a few hours).
GOOD LUCK