Thanks for the reply. I didn't know the profiles impacted wether or not the headset would work with the phone. Currently I have tried the outdoor and normal profiles, each of which have not worked. As for the pairing mode question, I'm pretty sure it is in pairing mode. I removed the device from my old phone's bluetooth section and then turned on the headset. This promted a message saying the headset was in pairing mode and asked if I would like to connect.

What other issues may be causing the connection to not happen?

thanks again in advance