As stated I'm using a Nexus 6 with my 4100NEX & mostly connect with Android auto, but sometimes I don't have time to find the usb cable & just connect with Bluetooth alone. But I've noticed that randomly my connection to the stereo is forgotten & I have to pair the device connection again. This happens on average 3 times a week. Has anyone else experienced this & /or know of a fix or root cause?

I have AVIC F20BT with Apple!
I can not say anything about your 4100NEX

I have the same with a Pioneer F77DAB (European version of 8100NEX) and Galaxy S6 Edge. For what it's worth, I also mostly use it with Android Auto. Haven't found a solution yet.