Is the headset in the pairing mode? With the headset turned off, hold in the power button on the headset until you see the light on the headset flashing red/blue, red/blue. If that isn't the case, try doing a hard reboot of your phone and then try pairing the headset to the phone. If you are still having a problem, do you by chance have another phone you can pair the headset with to see if the issue follows the headset or the phone?
