After I was unable to connect my old Bluetooth headset to the Nexus One, thinking it was a version incompatibility, I went out and bought a new Plantronics Voyager Pro, running Bluetooth 2.1. Still could not connect initially because the Nexus One would not recognize the device. You can imagine my frustration. Turns out the secret, at least for me, was in the order of steps in the pairing process. The following worked: - Turn the Bluetooth function on the phone on. - Set the phone to be discoverable. - Turn the headset on and set it for pairing. - After the phone gives up and stops searching for a device, manually tell the phone to search for devices (by tapping the search option). The key, at least for me, was to manually tell the phone to search; it will not find the device (neither of two devices in my case) when it searches automatically and I discovered this only by trial and error. Hope this helps someone.