Something got messed up on Apple's servers, lots of people are getting this. I spent hours trying to fix it last night and I think I made things even worse (I ended up locking myself out of two older Apple ID accounts, and creating two new Apple IDs I didn't want).
For now, I'm just going to wait a little bit and see if it gets fixed. Apple is going to have to take some action here because it is literally costing them, and developers, money (can't purchase or update anything until it's resolved), and creating a lot of ill-will among users. Especially if you're a new Apple user who just switched from Windows or Android, this is a terrible introduction to the Apple world.
This most likely means you have a 2nd AppleID that has this same email address listed as an alternate email address for it.
Manage Your Account at
Check to see if any of your other email addresses or AppleIDs and family members email addresses or AppleIDs have your main email account associated with it as an alternate email… because if they do, it won't send the verification email since it's already verified to another account.
You may need to change your email account to a 3rd or 4th one to disassociate it with this one first; then on the Apple ID website there's a section that says: Not Sure if you have an Apple ID? Find Out >
This will help you find the name on the other account and if you cannot get in to that account you should be able to receive a password reset to it.
If you cannot find the account you can try emailing iTunes and/or call Apple and check if they can find the account that is still associated with the email address you are trying to use for this.
iTunes Support - Email Option:
iPhone technical support: (U.S.)
iPod, Mac and iPad technical support: (U.S.)
(if you call they MAY be able to grant an exception to the phone support of your device due to it being an account problem or iCloud problem)