First of all, thank you for Chromecast support, finally!
But. When change tracks manually, e.g. search for a track when one is playing and select the results I usually have to hit play at least five times before the track starts and keeps playing, it might start for a half a second and then pause. If I let the album, list or que play without touching it, it will usually works fine. Skipping to next track also seems to work.
I have Chromecast Audio and first generation Chromecast. I use Spotify from Nexus 5 (Android Marshmallow), iOS9 and Chrome from Mac OS 10.11. All up to date. They all have this issue.
Google Play Music, YouTube and all other apps/services work without any issues. Only thing that does not is Spotify.