This problem is very annoying. The issue happens after swiping the spotify window (open apps screen) away on a samsung device (I have a galaxy S8+), then attemping to play Spotify on Android Auto. The issue has nothing to do with the car itself and can be reproduced by opening android auto on the phone. (without being connected to the car) The only resolution I found is to either restart the phone or "force stop" Spotify in settings -> apps.
Steps to reproduce: 1. Open Spotify app. 2. Go to open apps screen and swipe away the Spotify window to close it. (Very common action to close windows on the phone throughout the day by either swiping individually or clicking the "close all" button) 3. Open Android Auto on the phone and attempt to play Spotify. Result - The error "Spotify doesn't seem to be working at the moment" appears.
Very annoying workaround to resolve issue: 1. Restart phone 2. Go into settings, then apps, click on Spotify, and click "force stop". Result - Next time you open android auto you are able to successfully play Spotify without the above error appearing, but the next time you close the Spotify window in the open apps screen the error will appear in Android Auto again.