Another strange turn of events. iTunes Match is suddenly working on my new iPhone 4S.
I had been using iTunes Match on my iPhone 3GS and iPad 2, which I was backing up with iCloud. When I got the 4S, I restored from my 3GS iCloud backup, and, though I could see settings for iTunes Match, even enabling them did not do anything. The iPad 2 continued to work.
...until this morning.
I had been oscillating the on-off button sporadically, seeing if my iTunes Match library would download onto my device, and, lo and behold, it did this morning. When I launched the Music app on my iPhone, I saw the data indicator spinning in the menu bar and I just left my phone alone. Although I had seen the spinning data indicate before when launching the Music app, it was brief. This time it continued to spin, and my music library information slowly downloaded.
I know this is of little consolidation to those who do not even have the iTunes Match settings in their iOS devices, but for those who could not get their libraries to download, this could be good news.
The only thing that changed for me between last night and this morning was adding more music to iTunes, which prompted my iTunes Match library to update.