Apple Store telling me that my AT&T password is invalid

Wirelessly posted (Mozilla/5.0 (iPhone; U; CPU iPhone OS 4_3_5 like Mac OS X; en-us) AppleWebKit/533.17.9 (KHTML, like Gecko) Version/5.0.2 Mobile/8L1 Safari/6533.18.5)

I never put in the billing password.

If you also have a passcode (second level security), try using that instead. That worked for me when checking my eligibility.

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.

If it was lower case use all caps. That's what I had to do. Weird I know.