Almost sounds like you don't want to have to go back to the store. Get angry, dude! They effectively sold you a second-hand product as brand new. Someone got to handle it before you did.
I like my electronics to be virginal where possible (you wouldn't believe how many electronic gadgets I have with that plastic film still on them) and would be ropeable if this happened to me. Fuck speaking to MS, call up DSE first and ask them what they suggest you do. Get angry over the phone if you have to... I find it easier to do than to get angry in person

(and chances are if you do that, they'll have it all ready to go for you when you get there without having to wait around for ages)