Yes! You can be sure that it has something to do with Bluetooth pairing to your vehicle. I have a 2 year old S4 on Verizon (bought it in 2013 when it was first announced). It has never had a problem. None at all... My old car had no Bluetooth connectivity. My new 2015 Chevy Equinox has Bluetooth. Worked great on calls through my phone for the first few weeks. Then, suddenly, the phone required a reboot after every car-paired call. If I did not reboot, then the next caller (either incoming our outgoing) could not hear me, and I could not hear him!! -- Even if I hit the Bluetooth disconnect button on the connected call. In my case, I could not even continue the call through speakerphone or handheld mic/speaker. The phone continued to show calls and ring, but no one could talk to anyone, until a reboot.
I have tried EVERYTHING described by others in this thread. I have not found a solution. If I use my Galaxy S4 with my car (works great for 1 call), then the phone must be reboot before placing or receiving another call. Before the reboot, the mic & speaker are DEAD.