Press on/off button of the headset and connect the charger (or keep the headset powered down for max 18 hours to clear the device memory). Try the pairing again.
When pairing an accessory with Nokia N9, the pairing may fail if the NFC tags are touched for too short period of time. The accessory may then get into a state where it needs to be reset before it can connect again. To avoid any issues when pairing Nokia N9 with NFC accessories, keep the NFC tags close to each other and wait until N9 shows blue “NFC” text on the screen as a sign of pairing (typically within 1-4 seconds).