I have the same problem. Everything is up to date date. Everything is on the same network. The only way I can fix it is to clear storage in the Spotify app in Android settings. When I do this I can cast to my Chromecast Audio for a few hours. Then when I come back it has stopped working completely. My other music apps don't have this problem so it must be your app. Please fix it quickly!
Deleting the cache and program files resolve the problem in the first relogin to the app. But once you kill the Spotify process on the task manager and re-enter again, the problem comes back again... Shameful
Same problem, chromecast ultra works flawlessly with every other app except spotify, that speaks for itself really. I can cast every once and a while but once it locks itself out you are stuffed. Spotify is actually my most hated app in terms of bugs currently. This should be a priority 1 bug IMHO.