It depends. Usually if they send you a new phone it's because they have run out of refurbs or a particular phone has just recently been released. But you cannot count on new.
I had my HTC Touch Pro replaced in mid-2009. Brand new, less than two months old and they gave me a refurb. My wife's Touch Pro was replaced in 2011 or so and by that time Asurion had run out of Touch Pro stock (new or refurb) so they replaced it with an HTC Touch Pro 2.
Just depends what stock they have on hand.