Can you try a clean install?
[GUIDE] How to fix common issues for Spotify on Android
Hi,
the solution that works for me: an app killer, such as "ES Task manager" (good app by the way), "kill all" and then it works fine again. much fatser than rebooting. An app killer is a useful tool anyway.
Regards,