I did not clear AA's data nor cache, but it suddenly started working again this morning. The only things that I have done are reboot the phone since my testing last night (because it was still showing as connected to my car) and insert the Navigation SD card back into the car (which I'm not sure if this is connected at all). Suddenly I was prompted to add my car to AA and after a few connection retries it finally launched on the CMU. So I'm not really sure what changed because nothing was working last night despite several reboots of both systems. The only Google application that updated since then was Gmail. Facebook Messenger was also updated (that does have the ability to forward messages to AA, but I wouldn't think it would interfere with the connection). So I'm rather at a loss. I just hope it keeps working as it's been fine up until this point.