Uninstall SPotify on your phone and restart both devices. Reinstall Spotify and try again...
I have the same issue on both my Android TV and my Chromecast. Very annoying.
Try unlinking the Spotify account and re link it back that should work
Tried that but it won't let me unlink!
I have uninstalled and reinstalled spotify on my android. I have tried restarting google home. It used to work until this week. I have spotify premium which plays fine on my phone, but not on the google home speaker!