I have a wireless stereo headset (Motorola) that worked great with my iPhone 4 but won't connect to my iPhone 5. I recently bought an inexpensive "in ear" wireless device (Plantronics) that works great and even allows me to listen to music and use Siri. It's not stereo but it works. I would really like to know what the difference is if Bluetooth is a standard.
Bluetooth is a standard, but it also has multiple supported profiles. It also comes in a series of continuously updated versions or releases. Like any electronics standard (USB, SATA, wifi 802.11/a/b/g/n, EDGE, 3G LTE, ...) it continually changes as technology progresses.
Your iPhone 5 supports Bluetooth version 4.0. While it is largely backwards compatible with older BT releases, it is always possible that a much older bluetooth device (say one with BT 1 or 2) may have some incompatability with newer BT devices.
Also, some headsets only pair with one device, and need to be reset to discoverable mode to pair with a new device. Did you check the motorola documentation for yours to be sure you forced it back into pairing or discoverable mode before trying to connect to the iPhone 5?
P.S. Bluetooth is also not secret - all the information you could ever want (and likely more then you ever will) is readily available