Had this issue and it drove me nuts every time I checked it. Searched for a solution for the problem and it brought me to this thread. I ended up doing a couple things, and seems to work now... Here's what I did:
Logged out of my Spotify Accounts on my computers (have it on two computers, one was currently active/playing)
In the app, I clicked on the little icon next to Playlists at the top to bring up the menu and tapped on Settings
On that screen, I went all the way to the bottom and clicked on "Log out" to sign out of Spotify, then closed the app.
Restarted it and got the "Welcome to Spotify" screen, with the two login options (Facebook or Spotify.com details).
I logged in again, in my case with Facebook, and was back to my Playlists screen.
My Spotify was no longer offline and I could download some of my playlists (I'm a premium user with that option). I thought, cool at least I could download my playlists and listen to them offline now (it would always hang on the download before at 0% with the spinning indicator). To my surprise though, I clicked on some songs on a playlist I didn't download and the song started playing/streaming. Even better. It works again!
I didn't do a full debug, but I had spotify open and logged in on two different computers (my laptop that I work from away from home, and a desktop at home). I notice when I started playing a song on my computer, the app streaming would pause and vice versa. In fact, in the program it pops up a little message that says "streaming has paused because we've detected spotify being run somewhere else" (or something to that effect).
That doesn't bother me though, I'm just glad it works again on my phone.
I'm using Spotify for Windows on the computers and my phone is a Samsung Galaxy S / Epic 4g.
Nonetheless, hope this helps someone who is having the same issue.
Thanks to the person earlier in the thread who mentioned Spotify's location limits. That lead me to wonder if, at least for me, it got hung up somewhere between all the places I had it open and prompted me to log out of everywhere and then log into it on the phone first, then on the PC.