When I worked there, the Genius Bar always had an ample supply of replacement phones, starting on the launch day.
Replacement phones can either be brand-new or refurbed. My experience is that right after a launch, the replacements are all brand-new, and refurbs will slowly make their way into the replacement pipeline as returned iPhones get repaired and reused.
This is true...I had my iPhone 4 replaced the day after launch day with a brand new replacement (I asked the genius about it and she said all of the replacement phones they have right now are brand new and made especially to replace any early units that may have manufacturing defects)...