Are you storing a large amount of offline music on an SD card? I've had that cause issues for me in the past. Their guide to fixing issues[0] is generally worth giving a shot.

[0]: https://community.spotify.com/t5/Android/COMPLETE-GUIDE-How-...