I had an issue like that with a friends car. We got it working by turning off the bluetooth on the phone, starting the car, then turning the BT on again, and then pairing it from the BT menu.
It was a little quirky, and sometimes would need a rescan after the car was turned off.