You will want to read the fine print to know if you got screwed. You might also anonymously call several Verizon stores and ask them whether you would get a new phone or a pre-owned phone. Get names. Speak to managers. Above all, do not identify yourself until you get answers.
That being said, I would be pissed if that happened. Your phone was less than 30 days old, and you might have gotten a phone that was far older - how would you know? I would hate to think I might be talking on a year-old phone that someone else breathed and sweated all over, and kept in their sweaty pocket. No telling what subtle, imperceptable sludge is in the circuits that might cause you more problems AFTER your warranty expires. If I bought a new phone and exchanged it within 30 days, I would expect a brand-freaking-new phone.