What kind of car?
I've read threads about this before and the general consensus is to delete the partnership between the phone and car, then re establish it.
Same thing happened on my wife's Lexus. Also, too many text messages stored on the phone can cause the same problem if you have a Lexus.
David