I had the same problem, but apparently not everyone does. The answer appears to center on using the extended battery. If I use the regular battery - even with a case - the sound is great on the other end. With the extended battery, people only could understand what I was saying if I took off the case. I even posted a thread on this problem, but no one seemed to have a good answer other than enlarging the holes around the noise cancelling openings on the back. I did this, but it didn't make much of a difference.
So, in my mind, it's all about the extended battery and it's bulging back cover. At least, with the regular battery in place, people have no difficulty hearing me AND I have a choice of colorful cases ... again. I'll add that I get a full day's regular use on the regular battery. No streaming music or movies, though. I'd plug it in for that, anyway.