I have iTunes Match running on my MacBook pro and had it active on iTunes 10 and now 11. I can access my music from the cloud on ATV without any problem by artist/genre/etc. But I cannot see any of my playlists.
I also have an iPhone 5 and my wife has the iPhone 4s. Both phones are able to show all playlists in the cloud. However, my Apple TV will not show my playlists. When I navigate there and wait (even for 3 minutes) they do not appear. I do have maybe 30 playlists, some of them in folders. However, there are 10 playlists that are not in any folders. While they show on the phones, none of these show in ATV.
I have run updates to match in iTunes and have updated the ATV to the most recent firmware that came when iTunes 11 was released.
MacBook Pro (Retina, Mid 2012), Mac OS X (10.7.4), Win 7 in bootcamp
For some odd reason, I noticed that when I created new playlists they appeared on ATV. So I simply created new playlists and dragged over songs from the old ones. Now the new playlists show on the ATV. No clue why the old ones showed on phones/ipad but not ATV.