Hmm - found today that my pulse elite headset wouldn't connect to the PS3. I don't use it often - so no idea when it last worked.
Reset method is a pin in the dongle for one sec then hold the vss/mode/mic mute buttons in while you turn on the headset - but it didn't help.
The really odd thing was that the headset stayed in connecting mode (2 rapid blue blinks every couple of secs even when you turn it off)
I've found exactly one post on the 'net that describes it:
So - let's see if draining the battery helps.