I actually was going to ask for help since I'm having the same problem but just figured out the issue - at least for my case but am hoping that this applies to other as well.
You need to turn off the background restriction on 'Google App' app. Strangely 'Android Auto' app data restriction...