Ok. So I was talking to Customer Service, and my second order got cancelled too. I'm not sure what the problem is, so can't really say if its a technical issue or if its because the MS Store is setup a certain way.
HOWEVER, I did speak to customer service, and after getting off the phone with them I have to say, that what tangledW said was true. They really worked hard to keep me as a customer. Called and gave me daily updates, kept me in the loop and have worked to ensure that I receive my order.
The customer support/service I've received over the last few years from Microsoft is probably the best I've gotten anywhere.
So for the moment I think I finally am talking to someone who's really trying to keep my order, so I'll give them a bit of leeway. I'm not even mad anymore because the guy I'm talking to seems like he genuinely wants to help.
Interesting thing is, I did look at alternative products (I've had a month to do so), and the thing that bummed me out the most was that this was exactly what I wanted, nothing else out there had the combination of features that the Band 2 has. My hiking friends (who picked theirs up on opening day) are very impressed and from checking it out, nothing really compares to it.
I wish I could tell you what exactly is wrong with the MS store online. Since most of you have got your orders I guess mine might just be bad luck.