I had this issue and tried all suggestions including the 'solution' listed here and also chatted to Spotifysupport but nothing worked.
In the end I fixed it by un-installing 'Lan Optimiser' that was installed on my work PC then restarted the PC and finally re-installed Spotify.
If you don't have 'Lan Optimiser' installed look similar software and try removing that. If your on a work PC and don't have permission to install/un-install software then ask who ever installed Spotify in the first place to try the above.
Spotify should have an option to run the desktop app in a different way like using a web frontend that still allows downloading songs to a local storage, this would solve this issue with a simple setting.