I've been having some issues with some of my more complicated Smart Playlists not syncing with iTunes Match. Here is what Apple's engineers recommend:
1) Create your playlists on the machines that have the music locally. Otherwise, weirdness.
2) Don't you time-based option. So 'songs added after 4/4/05' would be a no-no. Same apparently goes for '25 most recent songs'.
3) Don't reference other playlists.
4) Try to use normal playlists instead.
Normal playlists aren't a good alternative, but now that I know the rules, I can craft some smarter smart playlists that will actually show up on my devices.
Oh, and Apple is aware that these are annoyances and hopes to strengthen the smart playlist support for Match in the future.