One problem that I had, although in a different car, there were some contacts that had become corrupted and when the my iPhone tried to sync with the bluetooth in the car then system would reach the corrupted entry and start synching again and not connecting properly.
I resolved it by cleaning the address book entries I wanted and ensuring that they were on a Bluetooth group which is the one I now use to sync with the car. This ensures that I have a clean address to sync with the car and that I still retain all the other addresses. You can restrict or choose a group with which to sync in each bluetooth connection that you have from your phone.
Also with the car that I have, a BMW, there was a limit on the number of addresses that could be stored in the phone book on the car, which I think was around 250. This could be another factor.
The only slight issue was the adding of users to the groups on my iPhone but there is an App for that too which works great so small issue resolved.
When I upgraded to the 4S the issue of synchronisation happened again but all I had to do was to create a new group with my Bluetooth contacts and that resolved the issue. I came from a 3G to a 4S so I assume there were some updates to the address book app and the way it worked.
One way to test if this is the issue would be to create a group and add one contact with the correct information in all the address book fields and try synching the bluetooth in the car with this test group and see if the same issue occurs. Then you can test
Hope that helps