I've been having this issue since using the spotify beta introducing "Apps", now, even with the official version I still have the issue.
Basically what happens is play list folders appear and dissapear, playlists don't stay where I put them, they'll jump back to their original spot, sometimes to somewhere completely different. Folders will dissapear leaving the playlists in them. Sometimes, after adding a playlist, folders and old playlists that I've deleted in the past *reappear*!
This has basically made my ability to use the playlist feature useless as I can have no trust in my organization or that a new playlist will remain.
Is this something that is being looked at? Is there a way to have all my playlists, current and deleted, "wiped" from my account all together, perhaps to fix the problem?