Hey guys,
I also just started having this problem and have been searching for solutions. I've read claims that range from blaming it on your carrier, your phone, and 3G vs. 4G. Since this issue only just started happening I knew they were baseless. So I dug into my settings and figured it out.
If you open the settings on the phone app itself, I have the choice of "General" or "Calls." Select "Calls." There will be a place to choose "Voice Privacy - Enable enhanced privacy mode." Un-select this.
Your problems should be over.