I am having this problem too. The recommended solutions, as far as I can see, do not work.
I am on a Samsung 10.1 Note.
Spotify tells me I am offline and that no internet connection is available, although it was working fine yesterday.
I have checked the Offline Mode setting. It is definitely off. When I toggle it, it tells me that Spotify is in offline mode. When I toggle it back, it tells me that no internet connection is available (but of course it is; I can do anything else online).
I have tried signing out and signing in again.
I am not connected via Facebook and never have been.
I have tried restarting the tablet.
Are there any other recommended solutions that I have missed?