Can no longer pair my iphone bluetooth headset with 3GS since iOS 5 upgrade

[balfatale]

Since upgrading my 3GS iphone to iOS 5 I cannot pair my iPhone bluetooth headset. Anyone else have this problem and found a solution they'd be willing to share?
Thank you!

 

[mkrishnan]

There are other reports of it, both in these threads here and on the Apple Support forums. My 3GS did not have any issues pairing with my Motorola headset after updating to iOS5....