This issue can occur when installing Spotify to an external SD card.
Please follow these steps to fix the issue on a WP8.1 device:
1) Uninstall Spotify from your WP8 device.
2) Go to the "Storage Sense" app.
3) Select to "Store new apps on my SD card".
4) Reinstall Spotify