It resolved itself. After I posted this, I was seeing strange things in the desktop client, and the web client would not even show my playlists.
I do wish Spotify would post a status when they're having trouble, instead of leaving us guessing. Their Twitter ids did not mention any problems at the time.
I checked Spotify on my Galaxy Note 3 this morning, and saw the playlist I added on the web was there. Both new playlists are on the Mac client, Android tablet app and phone app.
So the issue is gone today, so that is good.
Yes this used to work fine, but now I can't get it to work at all even if I log out of my phone and back in again. It doesn't work when I search for something on the phone either. Maybe you could give us a sync button?