Forgive the obvious question... but is the headset in Pairing Mode when you try to add the device to your BlackBerry?
Usually, on Motorola headsets, the blue LED will be solid when the device is in pairing mode.
Your user manual which came with your headset should have all the details on pairing mode for your particular device.