This is a serious widespread problem, and wreaks of an antenna issue. Class action suits have already been filed for this specific problem.
Apple will deny the problem exists, just like they did the 3G antenna problem.
We have spent many an hour on the phone w/Jabra, Plantronics etc - they tell us they get dozens of calls a day like this. Supposedly, the IOS 4.x software does not know how to adjust the Bluetooth radio gain. A "reset network settings" will force the dynamic settings to factory, but the iPhone 4 will act up again within a day requiring another reset.
This issue simply renders all iPhone 4 / Bluetooth headsets unusable. At last count there were over 1790 posts on the Apple support forums about this. 4.1 was supposed to fix it, but didn't even come close. For now, your only headset resolution is a wired version.
The Bluetooth issue is supposed to be fixed with the iPhone 5 (January), as Apple knows they have a problem - but another admission would be worse than the first one. But for you iPhone 4 owners you're SOL with Bluetooth.