I have been having the same issue with spotify not on pc not connecting to my android phone. The only thing i hadn't tried was dissconnecting from my work wifi (the same wifi that my work computer is on) and switched to my cell 4G service (for my phone only). Now it is working with no problems.
I have a Denon AVR-X2300W receiver and Spotify had been working fine with it. I just tried to connect today from my phone and there are no devices to select from. So I tried from my laptop and that can only 'see' my phone but says "Unavailable for listening on" so I don't think it's a problem with my devices. Has there been a recent update that's changed something? I'm on version 18.104.22.1689 on my phone.
Spotify Connect worked fine for me for multiple years. But in the summer Spotify updated something and now I cannot play music through Yamaha RX-V775. We have four iPhones and two iPads and only one iPad can currently connect to receiver and play music normally. That one is running an old version of Spotify app. 22.214.171.1249. Others are running the latest version. Has Spotify ditched support for that receiver or is there a known bug, which will be fixed?
After my Pioneer receiver stopped working with Spotify in the latest updates, now I can't even listen 1 hour of music via my Chromecast without it losing connection with my Android. Even closing the Spotify App or reconnecting WiFi on mobile doesn't fix it. This connect feature is going worse and worse.
All devices could see each other except for my PC. And the PC did not see any other devices. Uninstalled and reinstalled on the PC and now it's working normally again.
Update: After my PC rebooted it broke again. Did another uninstall/install and it started working again. I then tried to uninstall, reboot, install, reboot. It is now working so I'm not sure if it will break again on next reboot or if that sequence somehow fixed it. I'll update again after next reboot.
Another Update after 1 week: No reboot, but it's broken again. Spotify please fix this!