Bluetooth headphones don't work on S1?

I got a samsung 'Talk and Rock' bluetooth headphones, and my phone can't find it when I'm searching or listening. Is it because of my phone or the headset?

I would assume the headset... I have prolly 50 different headsets and earpieces to multiple berries!
Posted via mobile device

I've been using the S1 for over a year and have never encountered an issue with the device not recognizing one of my Bluetooth headsets or the bluetooth system in the car. Having said that, there have been bluetooth issues (but the headset was still recognized, just didn't work) with some of the old operating systems but that seems to be an issue which was resolved with the 5.0 operating systems. Sounds like the problem is with your bluetooth headset or some procedural error. Hope you figure it out.

EDIT:
Apparently, you are not alone. A quick Google search indicates many questions about pairing Samsung headsets. Not certain which headset you have but here is some additional info re most Samsung headsets and the WEP200 specifically. In particular, the button must be held for at least 7 seconds until there's a continuous glow of the indicator in order to achieve pairing mode. From what I've read, this may not be well stated in the instructions. Hope this is helpful.
To pair the headset in manually pairing mode:
1. With the headset off, press the center POWER button for 7 seconds until you see the headset blue light turn solid blue (no loneger flashing).
2. The indicator light will turn solid blue, which indicates that the headset is in “Pairing mode”.
3. In the phone, you now have to add the headset to the phone's list of Bluetooth devices.
4. You have to enter a Bluetooth passkey in the phone. The default passkey is usually 0000.