I'm not buying the heat or length-of-call argument - in my experience this issue is very simple to recreate regardless of these other factors. I experienced this issue on my first call after picking up the phone the day after launch day, consistently up to today, and I can reproduce it within the first few seconds of a call even if the phone is cold and was previously turned off for hours.
In my experience, I make a call, put the phone to my ear, and depending on where the phone is resting on my ear, it immediately starts to blink on and off like a Christmas tree. If I start with the earpiece at the top ridge of my ear, it's not too bad. If I then slide the phone slowly down the length of my ear, while keeping it in contact with my ear, the issue gets much worse when the earpiece crosses the middle of my ear, then the issue seems to subside once the earpiece reaches the bottom of my ear. This is 100% reproducible for me. The proximity sensor issue is definitely at its worst when the sensor is over the middle of my ear, which is the deepest part of my ear (leading to the ear canal, etc.). If the sensor is over a shallower part of my ear, the issue is either much less noticeable or disappears altogether. Again, this is regardless of heat, how long I've been on a call, etc.
Another point of interest - if my son holds the phone to his ear during a call, no matter where on his ear, we cannot reproduce the problem. His ear is much smaller and shallower than mine. This leads me to believe it is an issue with every phone, and some people may not realize it because of how they're resting the phone on their ear or due to their ear shape. I already have to hold the phone a certain way to not kill the reception, I'm not going to deal with resting it a certain way on my ear to avoid the proximity sensor issue.
Until Apple releases an official statement (if they do), I don't think we can be sure if this is a hardware or software issue, or a combination of both. Being a former-hardware-now-software guy, I would think this could be alleviated in software, but it depends on how much control the software has over this sensor.
@CellPhoneRepairs, I hope you're right in what you're saying re: Apple having fixed the issue in all the new iPhone 4's coming off the line, but that would mean it was indeed a hardware problem. If that's the case, and as others have said, Apple's going to be in a really tough spot with the millions of phones they've already sold. Apple left me a message earlier this weekend that my replacement phone was ready. I'll go in this week and check it out, but I'll refuse the phone if it exhibits the same issue. At that point I'll have a couple weeks left before my return period is up, I'll hold out until the end and if there's no fix, I'll return for a refund and not look back. I've bought Apple exclusively since the late 1980's, so this is very troubling for me. No company is perfect, and if the iPhone 4 is Apple's "Vista", I sure hope they make it right somehow.