Did you remove the old email address from the account? To change the email address for your account, you need to add the new address a secondary email for the account. Then you need to verify that new email address. Once that's done, you can change the secondary address to be the new primary address. Finally, you remove the old email address (which is now the secondary address) from the account. Unfortunately, some people stop after they add the new email address to the account as a secondary address. That doesn't work though because the primary email address is the only address used for sign in codes.