I got my first one replaced when the camera shutter wouldn't open, or the image would freeze.
They pulled a new one out of a different box that was individually sealed. It's considered refurbished, but she mentioned that it's since the iPhone 4 just came out, it's obviously new off the same manufacturing line, just reallocated for warranty replacements only.
Looked, felt, and smelt new to me. I was out the door in 15 minutes.