I had a similar problem when changing cell phones recently (could not pair the new phone). As often happens the solution turned out to be in the manual. My understanding is that the headset can only be paired with one device, so the old device needs to be "erased" from the headset before it will pair with a new device.
from the manual:
If the Bluetooth indicator does not flash alternately with the power indicator, or if you are trying to pair a headset that has previously been paired with another phone, you will need to press and hold the Bluetooth function button for 5 seconds in order to put the headset into “discoverable” mode.
Hope this helps (it worked for me - once I finally looked at the manual). Apologies if you have already tried this.