Spotify app won't connect to the internet

[_nonameftw_]

I've always had this problem with the Spotify app, and I've always updated it and I am currently using the lastest version. So there problem is when I open up the app, it says I don't have any connection to the internet and it won't let me search, browse artists or discover. I can however browse my own playlists (only the songs won't load on offline lists). I always have to either go to Browse and refresh a whole bunch of times or restart the app numerous times before it finally decides to connect.

[Joe]

I had something similar on an old phone. Try reinstalling spotify following the steps here.

[user-removed]

Same problem with the latest update for Android. 

[_nonameftw_]

Already have reinstalled it many times over past couple of months, never solved anything.