I just had a Pioneer AVIC-8100NEX professionally installed in my 2015 Subaru WRX. My cellphone is a Google Nexus 5 with Lollipop 5.1. And yes, the first things I did were (1) do the Pioneer firmware upgrade to 1.03, and (2) install the Android Auto app on my Nexus 5.
When I connect the phone via BT & USB, it all seems to work fine. The "APPS" icon turns into a "Android Auto" icon. The phone running the AA app seems to be properly recognized.
When I then press the icon, I get a problem message
“Android Auto cannot connect right now. When it is safe to do so, please check your Android phone.”
What is it that I must check on my phone? The BT connection works and I see the shared Google contacts. The Android Auto app is installed and running, and that infamous AA app check box is OFF.