I'm having the same behavior, I noticed that sometimes the app (Bluetooth Phonebook 1.2.4) shows on the "Enable PBaP" -> "State":
"License Check Failed !"
And the app doesn't show as connected, but I can see at the car screen that Bluetooth is connected, contacts are synced up (wrong contacts, not the contacts in the defined group in the App).
I have to turn off the Bluetooth on the phone, then turn it on and wait in the App until it shows "Ready" and then "Connected to..."
(sometimes I have to repeat the process because instead "Ready" it shows "License Check Failed !").
Unrooted Android 5.0.2, Samsung Galaxy Grand Prime.
Bluetooth Phonebook 1.2.4
I think it started to happen with the last App update.
Deinstalling and installing the App doesn't solves the problem.
Any ide on how to solve this problem?