Experienced the same issues as everyone else - no problems using BT on the original iPhone or the 3G, but the 4 made using the Prime 2, BlueAnt T1 and Voyager Pro unacceptable because of connection issues, the need to hold the phone next to the headset to maintain signal, muffled sound, etc.
Just tried a Sony VH110, a new very basic model from Sony, and have had zero issues with it. It's been more than a week and I'm on the headset a good 7-9 hours a day during the week (it says it lasts 10 hours of talk time, which I haven't gotten to yet). No drop-outs, I can walk away from the phone more than 3 feet without loosing service and no muffled sound issues (well it did occur once, but was caused by poor cell service, as the call failed shortly after the complaint that it was muffled).
Not sure why the Sony headset works, when others don't, but I've gone from hating the iPhone because of the BT issues to again enjoying using it.