It isn't a 'bluetooth networking' issue. It is a problem in the bluetooth stack and a corruption of the configuration. As the original hint says, even doing a full reset only helps temporarily. I had this problem myself. Doing a "Reset all settings" on the phone, which includes Bluetooth, would help briefly, but the problem would return, usually in less than a day. Doing the clean install is the only long term solution found so far.

Yes, it sucks that all settings will be lost. Unfortunately, this is a side effect of the closed nature of iOS. Apple has not even formally acknowledged this as a problem, but I can tell you that it is. Before the fix my bluetooth speakerphone was quieter than the speaker on my iPhone4. Sort of useless for a handsfree device. The speakerphone itself was very, very loud, as it has it'd own voice and sounds that it uses for feedback. But any audio that came over bluetooth was inaudibly low. A clean install worked perfectly and it is now as loud as it was with my 3G and iPhone OS 3.x.