spotify version for Windows phone is quite crap, but double check your free space ... It helped for me. Or sometimes it just takes long (maybe because of their special peer-to-peer technology of sharing music) but it happens on the other platforms too.
Anyway, they should update WP version because it's just not comparable to other platforms' versions. And we pay the same..
I know you are working on the WP8 app, and that it's not your top priority. iOS, iOS, ,iOS, Desktop, Andorid and WP8 – in that order. But please, any time frames on a fix? On an update? On Spotify Black?