Hi, I have a regular problem with slow connections when trying to connect to a Chromecast. It can take ~60 seconds. The only way to force it to connect is to quit the Spotify app completely and then try again. This even happens if Android has just been restarted. No other apps have exhibited casting problems.
Spotify Premium on Android, version 188.8.131.528
Chromecast Firmware: 1.40.156414