Yep - sucks. Here's the workaround I use, and it's been working for me. I have a LG G3, these steps may not work with your phone.
First, unpair/delete the phone.
Reset Buetooth factory settings.
Initiate connection with phone. (Pairing code etc...)
When NB1 requests access to phone history/contacts, UNTICK "don't ask again", and ALLOW.
Do not allow access to messages (more on that below)
5 minutes later (in my case LOL), phone will be connected.
Turn off car, restart.
NB1 will request access to history/contacts again, Tick "Don't ask again" and DENY.
I also deny access to messages forever - it seems that if I let the NB1 access SMS, then it also is allowed access to the phone book and starts downloading. I'd rather lose SMS read functionality since I didn't have it before...
What happens now is, on startup the NB1 will connect to the phone, try and d/l the phonebook, fail and finish setup. The previously stored phonebook is not deleted.