Welcome to the Android Forums!
Unfortunately what you describe is not unusual with Bluetooth devices. It sounds like either there is a bluetooth profile on the phone that the car stereo does not support... or, more likely, that there is a compatibility issue between the bluetooth stack on your phone and the bluetooth stack in the car stereo.
The only thing you can do to try to resolve at this point is likely to check with your stereo manufacturer (or car manufacturer is the stereo is factory stock) to see if upgraded firmware is available. If it is, install it per the manufacturers instructions and see if that resolves the issue you are encountering.