You know, the same thing happened to me back in July. What made it worse for me was that they were "out of stock" of the white box ones at that point, but had plenty of "new" ones in the store. But, since I bought it at AT&T, i was SOL. I had to wait several days, for their white box stock to replenish.
What is so maddening about all this, to me, is that the hypothetical guy next to me had the same problem, but he bought his at an Apple store, instead of an AT&T store, so he gets a new one on the spot, pulled out of a new box.
Treating the people who bought it at AT&T differently from the way they treat the people who bought it at Apple store is unacceptable, since they don't advertise ANYWHERE that there is ANY difference between the two, in that regard.
So, all of you who say - "oh come on, white box phones are fine, stop whining" to people who have problems the day after they bought their phones - you're not being fair. In my case, my replacement was delayed several days b/c of this policy, and my time wasted (waiting in line at genius bar TWICE and TWO trips to the Apple store, one to get them to agree to replace it, and then one to pick up the replacement after it arrived at the Apple store).