Just wanted to add my experience. I have a Plantronics Voyager Pro that worked fine with my G3 iPhone but does not with the iPhone 4. Same situation as with others posted here, I can hear who I call but they can't hear me. If it does work it is intermittent at best.
I called Apple and while the gentleman was nice, he blamed things on the headset and said Apple did their best to test but could not get all hardware done in the testing. He didn't tell me that the Plantronics device was or was not tested but did tell me that what was sold at the Apple store online was tested with the iPhone. Apple better check the what they list or the tech support should because there was my headset, the Plantronics Voyager Pro, the one that doesn't work, for sale. Other than that there was *no solution*, no suggestion to trade in the phone, nothing.
Please Apple get a clue, you are killing those of us that are trying to support you and purchase your products.