I've successfully paired 3 bluetooth headsets to my Sprint Touch:
1. Motorola H670
2. Samsung WEP200
3. Samsung WEP310
In all 3 cases, no one can hear me AT ALL. No matter how loud I yell.

So it just seems like the microphone part doesn't work. (I noticed the rare post about the microphone not working when paired with a Tom Tom, etc., but no real solutions.)
This was the case before and after the new factory ROM upgrade, so I don't think that's having any effect.
When I first got the phone, it worked fine with my old Motorola HS850 (but I gave that headset away thinking I wanted something newer & lighter), so at least I know it once worked.
This is driving me nuts. HELP!