I'm assuming OS X here based on the choice of forum, and not iOS based on the footer.
Please do not repeatedly change passwords or repeatedly fail passwords logins, or you'll risk triggering the evasion processing.
I'd expect Apple to send a confirming email message to the old email address when you manage your AppleID data over to the new email address, but the selection should otherwise remain. The mail message sent to the old address is intended to notify the user, should the account have been highjacked.
The email address is not tied to the AppleID password. Other than you'll need the password to log in and change the saved email address.
You'll have various prompts for passwords around Safari and iTunes that might remember the old OS X settings via your local Keychain, and you'll be changing those as you log in. (That's your local system applying defaults, and not anything at Apple.) You can either change those as you log in, or you can open Keychain Access and (carefully!) find and remove the old entries. (I'd strongly encourage making a backup of your keychain or of your system before deleting old Keychain entries.)
If something else is going on and you've verified the email settings are correct on your account, then you'll probably want to contact the folks at Apple directly.