AFAIAK, Bluetooth pairing has always been a pain in the butt, regardless of manufacturer. It's getting better, thankfully, with newer revisions.
You should be able to pair it via the on-screen settings menu on the phone. First, enable Bluetooth, then pair your device (this assumes you remember how to put your headset into pairing mode).