Bought my iPhone 4 when they first came out, and this problem just started happening. I first thought it was an AT&T thing, but I just got a free microcell from them, and the problem was still acting up, so a search and this forum came up.
Set up an appointment at the nearest Genius Bar a few blocks from work. Walked in, stated the problem, he called me and I heard him, but he could not hear me, then he checked the hold at the top of the phone (no blockage), and asked me if I wanted the Zagg Leather backing I put on the back of the phone as he was giving me a new one. No questions, though I did mention I saw that this was a potential issue, and I was in and out of the Genius bar in under 10 minutes.
And the great thing about is was that I had dropped the phone right after I bought it, cracking the back glass. So having a defective phone meant that I got my broken glass fixed for free. I've been an Apple consumer for many a year, mostly because of the quality of their products, but also because the few times I've had problematic products they've always addressed the problem quickly.