Hatte das selbe Problem & konnte es beheben:

Unter Mac OSX musst du zuerst die Spotify App deinstallieren. Dann öffnest du den Finder & drückst Command + Shift + G. Daraufhin erscheint ein Eingabefenster (siehe Screenshots), dort gibst du ein: "~/Library/Application Support/" (ohne die Anführungszeichen).

Dort solltest du den Ordner "Spotify" löschen. Danach einfach neuinstallieren & neu einloggen. Problem gelöst.

Unter Windows gibt es einen ähnlichen Ordner... Öffne den Dateimanager unter Windows & klick auf die Leiste, welche den aktuellen Pfad anzeigt (bspw. Computer).

Dort gibst du ein: %AppData% & drückst Enter. Darauf hin sollte sich ein Ordner öffnen, da kannst du den Spotify Ordner löschen. Danach wie unter MacOSX einfach neu installieren & neu einloggen. Problem gelöst : )

Alternativ kannst du auch Windows + R drücken & dort %AppData% eingeben. Ich habe das die Windows Lösung aus dem Kopf niedergeschrieben, die Ordnerpfade könnten auch anders sein.

Ich habe hier ein Youtube Video rausgekramt, welches das alles nochmal erklärt: http://www.youtube.com/watch?v=BZs8oBmxcI4