Weird - Okay, let's try and get this sorted. First of all, I'd recommend a Clean Reinstall on both your devices.
Failing that, it might be a connection issue. On your computer, check to see if you have any firewall / antivirus programs running. If so, add Spotify to the exceptions list. For your Android device, you might want to try installing this preview version.
I noticed after some upgrade that the proxy setting got changed to "auto-detect" and this causes Spotify to be off-line while it looks for a proxy. Edit/Preferences/Proxy and set to none. I also noticed my play list somehow got set to not available offline. That is annoying! Click on the playlist and select "Available Offline".
I have moved to Madeira (Portugal) to work and now cannot go online with Spotify. I have reinstalled and checked my firewall, all that's done is delete all my music. I have checked my Proxy, changed it to No Proxy, still nothing. I have tried to change my country but it keeps declining my card details.....I really need this to work now!!!!