I just solved this! Go to Spotify App Settings via your phone's settings page, go to "Mobile Data & WiFi" ad do the following: Turn on "Background Data" and "Unrestricted Data Usage". Turn off "Disabled WiFi" and "Disabled Data Usage". Immediately after I did that Spotify detected internet.
So this solution might be weird at first but hear me out..
If you have the app Genius installed in your phone as well with Spotify give them both unrestricted data access and also to google play games and store and infact google(app). Try to run Spotify then on your mobile data and hopefully there won't be an issue.