OK, how are you initiating the pairing, from the phone or from the headset? It may need to be initiated in a particular manner...
I know that usually the headsets are made discoverable, and then you search for it and find it on the device that you want to pair to it - but this one may be backward?
Also, are you rooted, and if so, are you running an alternate ROM?