I've had this problem several times with my phone and although it is somewhat of a pain (and I should not have to do this), I have been able to easily resolve it by:
1) turn off bluetooth.
2) turn the phone off then back on
3) turn the bluetooth back on, then
4) turn on your bluetooth headset or turn on your car.