not all headsets will work with all devices, so its not uncommon for a set to work with one device and not another.
what model headset are you using?
does it have the latest software update from its manufacrutrer?
what version of Android? 4.3? 4.2?
you are not rooted I ASSume?
you are an international user on an international carrier correct?
you say the issue "suddenly" started, so at one point the set was working fine with the phone?
if this is the case, did you install or uninstall any apps?
did you UN PAIR then RE PAIR the set?
do you have another set of phones you can test that are bluetooth?