Couple updates:
Right now, I'm speaking with a senior specialist at AT&T and they are saying this issue arises when the customer placed the order on store.apple.com and then changed the shipping address to something different from the original billing address (pulled from AT&T's servers at time of order). AT&T is saying that Apple has a special activation team set up to handle this. My senior advisor at Apple is not aware of this team, so AT&T is trying to track them down for me...
I had a similar situation with Verizon when I got my 5s. Activating it was hell, but eventually a Verizon specialist in the store for the iPhone 5s launch got it sorted.