I have been playing around with spotify a bit,
And I was so furious about this annoying problem that I started to go through this problem bit by bit!
The solution that's working for me was this.
I completely starting to pick out everything that my Samsung S4 Galaxy could do,
Battery, simCard and Sd Card (SanDisk Ultra 64GB). I connected my battery to the phone and connected the phone through USB to my PC (Win 8.1).
I started my phone, and once I got in the phone and started up Spotify and got an Error message that spotify could not find any Sd card.
So, I uninstalled the Spotify App and started to download it again, once I was log in I started to download one of my playlists, started to play some of the songs and it worked just fine. I added some local files in this playlist through my PC and started to sync it with my phone, I started to play that song and it worked. I Turned off my phone and turned off spotify on my PC, and started the phone again.
Started spotify and started to play the whole playlist (5songs) and it worked really good. I turned OFFLINE on and once more started the playlist and it worked, I closed spotify and started it again, started to play the playlist without any problems.
Turned off my phone (still in offline mode in spotify) and started spotify once the phone booted up, and all things worked great.
SO far my own conclusion about this problem is that since the last update on Android (4.3) i got some serious problems, and Spotify works Great when Spotify is installed on the phone and not on the SD card (if there is any option that you can choose where it shall install apps on please tell!),. But before i can Confirm this anyfurther I am in this moment sitting here and looks at my phone, SD Card and my sim Card beside the phone :P,. I will try to connect my SD card, and then turn on the phone and see if it works well, and then try the Sim Card.
1 Uninstall spotify
2 Take out the SD card and Sim Card
3 Start the phone and install spotify (without any card whats so ever inserted in the phone)
4 And then Sync all playlists
5 Play 😃
I will confirm this in a bit when my Phone has SD and Simcard installed again 🙂
Cheers (Hope this helped out a bit for ya guys and sorry for my english)