I'm experiencing this issue as well, likely have been since day one but it hasn't bothered me enough until I recently got a Fitbit and tried to pair/sync.
Phone was purchased the weekend of release from a Best Buy. I have three connected Bluetooth devices, a car audio system, UE Boom Speaker and now a Fitbit. I always noticed that the car audio would work fine, but the UE Boom wouldn't. I chalked it up to some issue between the two devices that I'd worry about later.
From reading this thread, it's obvious that the bluetooth issue is entirely with the phone. When not connected to Wifi (IE: In the car) I get about 10 feet of range and can put the phone in my pocket and have no issues. When Wifi is connected, the device literally has to be within inches of the phone. I can't use the portable speaker unless they are next to each other. Same now with the Fitbit. With wifi on, I have to have the phone sitting on my wrist essentially and sometimes hit sync multiple times.
My problem with a replacement, is that my phone was recently dropped (by a friend) and there's a small crack in bottom front glass. It's just over the back button, not on the screen itself, so my plan was to just deal with it since it doesn't affect the screen. But is there any way I can go to AT&T for a replacement and NOT have them charge me to fix the glass? I contacted Samsung about the glass and they quoted $240 for a fix, which I just can't justify. I'd be so mad if I went through a return/replacement, only to get billed or be told after a few weeks of waiting "here's your phone back, no fix unless you pay"
Any insight? I guess I can at least head to AT&T and see if they think they can do anything for me.