Like many others, I'm still having massive issues with my proximity sensor. Not just every now and then, but pretty much every time I use the phone. It's gotten to the point where I'm thinking about switching back to my 3GS; the 4 is absolutely becoming unusable. Every time I'm on the phone my cheek hits the mute button, speaker, hangs up... uh it's so incredibly annoying. It's been about 2 months of dreaded phone calls.
Will Apple Care address this with something other than "just re-install your software, blah blah blah"? I purchased it unlocked from the Apple website so it's an issue Apple will have to deal with and not my carrier.
It's both software and hardware. The placement of the proximity sensor makes it much more sensitive to light. When it was in the spot where the front facing camera is, it took a lot to set off the sensor. I could hold it between my ear and shoulder and it wouldn't have an issue because it was in a spot where light couldn't set it off easily.
Now that it's been moved to it's current position, it's much more sensitive to light. The ONLY way to permanently fix it is to move it back to its original location and switch the front facing camera to the other side. Until then, they'll just modify the software to calculate sensitivity the best they can.
In that case you may have a defective unit. You should definitely take it to the Apple Store for inspection and possible replacement. I know my phones proximity sensor issues were resolved with a settings reset. If nothing's helping you could have randomly just got a bad phone.
I took mine into the Apple store because my proximity sensor was giving me problems and they checked it out, and immediately replaced it! Very simple and easy.
But even now this new Iphone 4 is still giving me some problems -_-