Reset the headset. Some headsets allow pairing to only one device at a time.
If this is the case and it's already paired to your smartphone, it won't pair with another device.
Follow instructions that came with the headset about how to reset it, in Nokia headsets, you usually have to press and hold a button until a red LED flashes. After you reset, pair with the computer straightaway, not with the smartphone.