Wow, I've had this show up for a couple of days, which is what led me to read through all the pages. So much misinformation.
First off, it has nothing to do with DNS. If you have a working internet connection, iTunes Match will work.
It also has nothing to do with your router/modem firmware or how it handles network traffic. Some people even went so far as to say their routers were not compatible with iTunes Match. Seriously. No.
It has nothing to do with your set up. I enabled iTunes Match on my second Mac that had never been set up to use it, and experienced a connection failure from the get go. So, it's not machine dependent.
It also has nothing to do with your AirPort (Extreme or Express) firmware. I downgraded my 2ng Gen Express and it still didn't work.
Some one posted that he had an iTunes Senior Team member read through this thread and they concluded that anything that worked was purely coincidence. They were right. Nothing in this thread will lead you to fix the problem, not directly.
So why am I posting? Because I fixed it. How? Not sure, but it likely has something to do with credentials and how the iTunes servers respond to them. That's why the connection will go live if you go into your iTunes Account Purchased screen (in iTunes) and either download an app (or other purchase). You can also hide an app and it will reconnect.
What did I do? Toggled my internet connection and then signed out of everything. Deauthorized my machine. Then I signed by in and reauthorized it. It didn't connect, but I went back into my account and just hide on of my purchases. Reconnected. It didn't stay for long, but after it got knocked off again, I again, went into my account and did the same thing. This time it stayed up. Has been good for a day now. Before it wouldn't stay connected for more than 3 mins at a time, and go dead for hours.
This leads me to believe it's something to do with either the keychain or some server-side anomaly where iTunes will choke and drop the connection.
So I'm urging anyone that has this problem to dig into their account settings and re-establish the connection through either downloading or hiding a recent purchase. I had to do it only a few times, and it's been good.
In my case, the service has worked perfectly for over a year and these connection problems only showed up a day or two ago.