Yes, I'm suffering the same intermittent issue and haven't found a solution.
I also have an apple cable plugged into the second socket and this works fine on my work phone (I only ever have one phone plugged in but do leave both cables in for ease)
I've tried connecting with the Android phone locked and unlocked, before and after ignition is turned on, and plugging in before and after each option. Unfortunately I've not been able to pinpoint a combination which doesn't have the 'PIN required message'.
Oh and I did note that sometimes the SatNav will still work and appears to override the message.