I can say that the information they gave you is not entirely accurate. I have a Verizon Galaxy Note 4 and I was able to use AA just fine from around May of 2015 all the way through February of 2016. First was in my old car with a Pioneer NEX4100, and second was in my 2016 VW GTI with the Fender audio system from December 2015 until February 2016. During the entire time everything was good, I was on Android 5.0 and had to be on that version since a work app I use wouldn't work on 5.1.1. After February, we got the OK to update to 5.1.1. Immediately after the 5.1.1 update I no longer get any audio through Android Auto. No navigation, music, text, or even the "boing" noise when you press the mic button on screen. Something in 5.1.1 broke it, and I am patiently waiting and hoping that we will get 6.0 on the Note 4 and it will all start working again. In the mean time, I am using a 2 phone solution where I took my Galaxy s3 and put cyanogenmod on it to run AA, then have it connect through wifi to my Note 4 hotspot. Everything is god now except for the phone call situation, but i rarely take calls while diving anyhow, so it isn't the end of the world. If android 6.0 doesn't fix it though, I will be a bit more upset.