When you enter your main Bluetooth settings on the phone that shows the list of paired devices, does it display any icons next to the car's listing? In my case, it recognizes mine as a vehicle profile.
Also, is this a factory or aftermarket radio? If it's factory, what is the year, make, and model vehicle? If it's an aftermarket, we'd need the brand and model number of the stereo itself. It's possible that the radio just isn't fully compatible, so I was going to try and look into that. If you have the owners manual, that should verify if it has the media profile or not.