Like Glenn said, you paid for new, so you are entitled to new. However, if it doesn't bother you then you could settle for a replug (I'm actually not sure that can really be done), but definitely get some good will credit in exchange. They clearly owe you on this one.
If it were me, I'd go for the new tire, partly on principle, but also to test how they stand behind their product. Delivering a "new" machine with not only a used tire, but one that's been puctured and repaired, really calls into question the dealers practices. They should fall all over themselves appologizing for such a hideous error on their part. You can then decide if you really want the new tire or credit against their conscience. If they give you a hard time, then I think you've uncovered a rat.
Peter