Seems like Bluetooth has just stopped working on my new Curve this weekend. I just tried to pair a new headset and it isn't finding it. The headset paired to my laptop just fine. So I tried to re-connect the Curve to my laptop and that's not working either. All devices are in discoverable mode. Any suggestions before I call Verizon?

Sometimes when a device is paired up with multiple devices you need to "end/cancel/turn off" the pairing between the previous device before you can find it with the new one.

If you are referring to the Curve, it's not paired with any other devices. I've also just done a battery pull and that didn't resolve the problem.

Problem solved. Verizon replaced the phone. Everything works fine now.