I experienced similar problems. I called microsoft and they told me to hold down the microphone mute button on the remote for up to 10 seconds to "sync the headphones to the software". If not contact Microsoft Support, it takes a while but in the end it is always fixed. Happy

P.S. You installed the software that came with the headsets right?