FWIW, The Genius Bar replacements can either be new or refurbed, but they don't come in the original retail packing, unless you return your iPhone for a refund and purchase another one (which isn't usually done at the Genius Bar).
My replacement iPhone at the Genius Bar came from a thin white box. I got it replaced on the first day the iPhones went on sale, so it was definitely a brand new one.