The other smartphone cannot see my bluetooth device. Is this normal?
A phone that isn't already paired can only see the device while the device is discoverable. This is a special mode you put the device into (usually with a button or combination of buttons on the device). The manual for the device probably describes this as part of the pairing procedure. If you repeat this procedure, your new phone should be able to pair just fine.
So once a headphone is paired with a cellphone, I need to unpair that headphone before I can use it on other smart phone?
Not usually. The pairing process just allows the two devices to swap special data (encryption keys) to allow them to recognise each other in future. After pairing, both devices remember the key. It's no different from saving the key for a Wi-Fi network in your phone, except it works both ways.
While phones can remember lots of pairings (and show you a list of paired devices), devices like headsets are a lot simpler, and can only remember a few. Exactly how many is different from headset to headset. Once it's reached this limit, most likely pairing a new phone with the headset just makes it forget the first phone you paired. Unpairing just means forgetting the key: it's something either side (the phone or the headset) can do without the co-operation of the other side.
What about if I no longer have access to the original smart phone (say I factory reset the phone). What would happen?
Nothing happens, just like if you lose or factory reset the phone after giving it the key to your Wi-Fi network. Your headset will still remember its half of the key, but that half won't do anything any more. If you pair the headset with enough other phones, it'll probably overwrite that key with a newer one eventually.
