Although I installed Spotify for Android shortly after I bought my Nexus S, I rarely used it; when I have time to listen to something I tend to choose podcasts or audio books. So I couldn't say for sure when the Spotify app stopped working.
The symptoms were that I would start up the app, log in, and a few seconds later it would just quit. No explanation. If I started the app up offline (i.e., no wi-fi or 3G network available), there was no problem, other than not having any music to play. Then as soon as I went online, the Spotify app would crash.
I couldn't find anything about on it on the web, apart from one person who'd 'fixed' it by deleting all their playlists. He suggested it might be due to an awkward character in a song title. This fitted in with my experience, in that the program seemed to crash while synchronising data. Unlike him though, I wasn't prepared to chuck out all my carefully assembled playlists.
But it kept bugging me, and the more I thought about it, the less plausible this seemed. If it was really down to having foreign characters in a title, surely thousands of people would have been hit with this, and Spotify would have quickly fixed it? So maybe it was something else in my playlists. Looking at them on my PC, I noticed that several tracks had a sort of lock icon next to them. In each case the track could no longer be found via a general search, though an alternative version of the track could. I'm guessing that the original track is no longer available, but Spotify is substituting the replacement. So I went through and manually replaced all those tracks. Alas, it had no effect on the Spotify app.
All was not lost: while getting rid of the lock icons, I'd noticed a few 'musical note' icons. These indicate tracks which are local to your device. Could the Spotify app be falling over trying to synchronise music that was on my PC's hard drive? I took all the local music out of my playlists, and my Starred items, and a couple that were in my waiting to play list. And finally my Spotify app managed to start up properly.
So that's the trick: don't have any local files anywhere in your lists. I can log in just fine now. In fact, it's even better than that: I've just noticed I can't seem to log out.
Supplemental: My Android app is bombing out again, and there are no longer any local files in my playlist. So I'm back to square one, or maybe square two, as at least I've established that the problem's something to do with the playlists. I am not giving up on this though: watch this space.
Supplemental 2: I think I've really fixed it this time.