I couldn't play Spotify through my car stereo after getting a new phone. Turned out I could only have one device connected to my car for audio (and 4 for calls) so I deleted all other devices (as not needed and can pair again if I do) and when I connected up again it was working. Hope that helps. I have a Sony phone and BMW car in case that's important.
