I tried a simple thing.I cleared the app data from windows settings(rather than uninstalling) and then i downloaded a VPN and set its location to the country location I provided. I logged in and checked 'remember me'. Its not bothering me again and I can run spotify now and no need of VPN anymore after using it once. But even tho if you see that again then follow the procedure above again, just takes a couple of minutes.
I am having this same problem, with no proxy, no firewall, and it says I am in the right country. The problem is only with the desktop app, on my phone and play.spotify.com I can log in just fine. Even when I re-download the app, it still doesn't work. I've been stuck out of the app for a month.