What car model, year, etc.? Assuming its a factory head unit, otherwise what brand/model head unit? And if its a factory head unit, do you happen to know who actually manufactures it?
Unfortunately, the Bluetooth standard is not nearly as "standard" as you would hope. The sheer number of different devices and accessories made by different manufacturers means compatibility issues are fairly common; and also makes it difficult to troubleshoot such connection issues.
Try to delete the device from the car head unit, as previously mentioned (if you haven't already). Otherwide, try to see if your head unit has a way to reset or re-initialize the system. Just deleting the profile for the phone may not be enough. Such is the case with my 2012 Subaru Impreza head unit (made by Kenwood, from what I understand). Just deleting the phone's profile and re-pairing causes issues (phone will not auto reconnect whenever the car is started, need to toggle Bluetooth off and on again to connect). But re-initializing the system on the head unit (then re-pairing the phone) fixes this. Unfortunately, this is completely in-obvious and not well documented. The only way I found out about this is from a XDA member that happens to work at a Subaru dealer and happens to be there "tech guy".
Please click the "Thanks" button if you found a post helpful!
Phone: AT&T HTC One (M8)
Tablet: Samsung Galaxy Tab Pro 8.4 (WiFi only)