iPhone 5 - I have this problem as well.
Store would not replace it as they couldn't reproduce the problem within a minute or so.
Basically, I'm muffled and/or garbled to the other party almost all the time.
However, with a headset, the quality is great - so it's not the network.
The only time I can be understood without a headset, ironically, is when there's a decent amount of background noise. When I'm someplace quiet, that's when the problem is worst.
Given this, I'm suspecting issues with their noise cancellation.