I Had the same problem. Solved
When checking out of the Apple Store to buy the iPhone 5 the eligibility page would ask for my billing password if I had one, otherwise put your billing zip code. No matter what I did it said I had to provide a billing password and when I did it said that password is invalid. I confirmed that the billing password is what AT&T calls your security pass code and the password I was providing was correct. It is the second password you enter after logging into AT&T wireless online. However my password was so old(from Cingular) that it was alphanumeric because at the time I created it that was the format. Now the security password/billing password is ONLY allowed to be numerical. I changed my security pass code on AT&T wireless online to a numerical password and was finally able to complete my purchase on Apples website.
Simple, after 7 hours of trying to buy a phone. I hope this helps others.