It is possible that you have np connection or it is weak. Spotify can stream on mobile or wifi home connection. Speed should be over 1 Mbit/s, but it may work also on 512 kbps. Please if you have problems streaming, try Offline list, if possible, or re-install app / reboot your router / mobile connection.
I often have trouble connecting on BART. I'm browsing the web and typing this while down here, but Spotify won't connect. It's the only program that has ever said it can't connect on this phone. And what is with the nonexistent customer service?