How do I get App Store to recognize my Apple ID?

I setup my User profile on a macbook and I can log into Apple Accounts with a newly created Apple ID. When I sign-in to the App Store, it says, I need to review my account information and pre-fills it with my Apple ID. Great so far. After entering in the password and security questions (and accepting the agreement), it says that this email is not available to use as an Apple ID - that I may already have an Apple ID associated with this address. Well, OF COURSE I have, I just created the Apple ID on apple.com/accounts. What's going on?