I had problems with this issue and came upon a solution which may help many Android users. There is an app named "Bluetooth Phonebook" which simply updates your phone's PBAP (Phone Book Access Profile). It's a bluetooth profile used for the transfer of contact data between a mobile phone and a car. The free version of the app allows you to try it out and see if your contact info appears in your car, but it changes one digit in each phone number as it transfers to the car. Your data on the phone is not changed. If it works, you can simply buy the paid version of the app for about $2 and your problems are over. Hope this works for you!