"paired but not connected" headache - any help?

[Hawaii Built]

I recently bought a Samsung hands-free bluetooth car headset and successfully paired it to my HTC Sensation last week. It stayed connected for about 3 hours - I've been able to connect it once more for an hour or so but did not know what I did to successfully reconnect it. I've tried pulling the battery and SD card per T-Mo customer care, switching the headset and phone on and off in various order (phone first, then headset first...), turning the bluetooth function on and off, un-pairing and re-pairing, and manually hitting the connect button in the bluetooth menu of the phone. It still reads "Paired but not connected"

Is there a solution to this?