I'm having the same issue. My phone is a Galaxy S6 and the microphone will work fine when the headphones are disconnected. I've tried numerous pairs and cannot talk with them plugged in, though last I checked, have no issue if plugged into the auxiliary cord in my car. None of the pairs I'm using have a build in microphone that I know of and one pair is the original pair that came with the phone.
Riddles