Once I've created playlist Starred because I was unable to add few songs to original one (really weird).
Today on one machine (ubuntu 14.04, Spotify 0.9.17.1.g9b85d43) I've deleted the "second" starred and the original one left (it had star icon). Everything worked fine.
After turning off and starting second machine (arch linux, Spotify 18.104.22.168.gb8a7150f) i find out that i have no "starred" playlist - even original one dissapeared.
I feel really frustrated about loosing all my music in that playlist.