Weird. Normally, they should have replacement devices ready to go. At this point, since there hasn't been much time for refurbs to be built, a replacement device would be new-- just not in retail boxing or with new accessories.
However, if I were you, I'd just return your detective unit and repurchase a brand new one. Especially if they're showing the model you have/want in stock. That's what I did. My unit was having screen issues, so I just returned it and immediately repurchased a new one (I also purchased a different color, since I ended up not liking the silver as much as I thought I would).
EDIT: Ah, just saw your point about having purchased from Verizon. Yes, if you purchased from Verizon, your options are to return it to Verizon and repurchase or accept a replacement device from Apple. If you didn't purchase it directly from Apple, you can't very well return it to Apple for a full exchange.