Originally Posted by DocT
Fix for this is counterintuitive. When you start your phone or restart bluetooth go to Settings>Applications>Running Services. Look for the Service "BluetoothPbapService". tap it, then hit stop. This removes it from the list. The phone pairs and uploads the phone book without problems until you either stop and restart bluetooth or turn your phone off. I am looking for a developer who can automate this process with an app without rooting the phone. Hope this helps.
Update: I first tried it with the service running and connection eventually failed. I then stopped BluetoothPbapService and tried again and the connection was successful! So yes indeed we need to find someone that can program something to automatically do this.