Hi there,
As a note, the bluetooth headsets do not actually connect to the phone untill you are in the phone "mode" (at least this is how it works on my iPhone with a Moto H700). have you tried to actually make a call withthe headset?
I hope that this helps.
Thanks,
Rob.