I have the same problem every time and it is seriously driving me crazy. I hope someone has a work around or Spotify has a fix for this soon. Between this and the track not updating on my lock screen or car stereo, I am annoyed.
I have the same exact problem and it is too driving me crazy any updates correcting this error? It does not happen so much at home where I have really strong wifi. I happen to be in a week wifi spot at work therefore I wonder if that has anything to do with it or not. Also I wonder if 3G and wifi are fighting each other as a consequence I have disable 3G to see if it works better but it still does it.
This is me letting you know that this bug interferes with the functionality of the app. Here's why: Before this error pops up, the Spotify app spends a few seconds trying to connect in the manner it had been connecting the last time the app was used. When it doesn't find the network is was connected to earlier, it throws up this error. The user then must click OK before being able to browse for a track to play. It's just unexpected behavior that occurs usually when switching from WiFi to 4G.
Steps to reproduce the error: On WiFi, launch the app and allow it to connect. Then open the Settings app and turn off WiFi. The phone is now on 4G. Switch back to the Spotify app and you will receive the error.