I, too, have the proximity sensor issue. Since day one, both my friend and I have noticed calls muted, disconnected, keypad buttons pressed, extra calls made, conversions to facetime initiated, all during calls to each other on our iPhone 4s. Both of us tried the "Reset All Settings" fix a week ago. The issue persists for both of us.
Frankly, I could care less about the antenna issue. I always intended to protect my phone with a case, and the signal issue therefore is moot (for me). The proximity sensor, however, doesn't have a convenient workaround.
After 105 pages of this thread, I still do not know whether the issue warrants attempting to get a replacement phone, or if this afflicts a majority of the devices?
If this were really a software problem, wouldn't we have seen a stealth software update by now to quietly fix it? Clearly it can't be that simple.