Android Auto not working

[chrisreddall]

Recently Spotify has stopped working with Android Auto, both in the car display and directly on the device - Samsung Galaxy S8. Cannot play music and it does not show anything in the library. This has only stopped working in the last 2 weeks or so. If I completely reboot my phone it works once but then stops working when I try it a second time.

[raindoggbknyc]

Brand new Galaxy S9, Updated software, all deleted and reinstalled multiple times. No Luck. 

Driving a 2016 VW GTI