I've been having the same issue as everyone else for about three weeks now. I first called Apple Care, who transferred me to the email iTunes support. The last email I got from them was that the person I was in contact with didn't know how to fix the problem so he was passing it on to his supervisor, to which I haven't heard from yet. If I hear anything from them, I will soon to post it. A brief synopsis of what's going on in my situation:
AT&T customer (grandfathered unlimited plan)
Apple iPhone 5 (iOS 6.0)
iTunes match renews mid April
The problem, like many others only happens when I am connected to the cellular connection. Under wifi, it works perfectly. Once I leave wifi, it stays connected for a few minutes, then gives the dreaded message that I am not subscribed to iTunes match.
As far as settings goes, under iTunes and App Stores, I have Use Cellular Data toggled on, which the Apple rep suggested I do. I did that and problem still persisted. That's my situation, which sounds like is very similar to others as well. Once I hear from the supervisor, I will post what he told me. Hopefully they can fix this, and soon. I purchased a 16GB model because of iTunes match, (due to 20GB of music streaming).