Is it a stereo headset that supports a2dp?

I've had issues in the past when I've paired my iTouch4g with more than one device.
And then used a2dp on both of those devices.

Sometimes if a BT client (in your case the headset & car stereo) is multi-pair...
It doesn't support multi-pair of exactly the same profile type for more than 1x device.