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 un-installed Spotify, then restarted PC and finally re-installed Spotify.
If you don't have 'Lan Optimiser' or similar software installed try removing all bundledPC manufacturer software and try a re-install. For example if yourPC is made by GIGABYTE then remove all the software by GIGABYTE (most of it you don't need and does nothing but slow your PC down anyway). Please be careful not to un-install any network drivers!