Same for me. I've always looked for playlists of any kind of music but now I can't find any playlists. As you say playlists have gone from the app. And for Mac OSx or windows versions, it's happening the same, although you can search them by typing "playlist:" and the name of the playlist you want to find. I hope this will be fixed soon, cause I think is one of the best things Spotify have.
Hi again, it seems like, at least for me, it has been fixed. I'm now on my windows spotify, I have looked for "cena" ("dinner" in spanish), and some results have appeared as playlists, apart from albums and artists. I think something wrong happened but they are trying to fix it. Apart from that I have red that a lot of users lost their own playlists since las update, so I think they are recreating them.