That, the App Store, and Facetime are the 3 places where you'd need to log in to Apple's services. If a logout/login of those doesn't fix the issue, then I'm stumped.
I just had to deal with this with my dad.
Facetime, iTunes/ App Store, and iCloud all need to logged in/out separately.
What's happening is that one of them is still looking for your old email address (which now is dis-associated with your account), and it's getting FREAKED OUT, MAN!!! You're dealing with 2 user names (user.old and user.new)
1:
https://appleid.apple.com/ > Manage your Apple ID
2: Log in to your Apple ID (user.new and password)
3: On the right side, in the middle, Apple ID and Primary Email Address
3a: You should be seeing your user.new email address listed, click 'edit' to the right
4: Type your user.old email address, and save
5: On every device log out of FaceTime, iTunes, the App Store, and iCloud
6: Repeat steps 3 and 4, but with your user.new email address
7: Log back into all the services everywhere
This is a prime example of things going straight to hell when they don't 'just work'. I spent about an hour and a half on the phone with Apple Support after my dad got his new phone because he updated his apple id and nothing told him "hey, before you do this, you need to do all this stuff, like log out of things". The email address IS the ID, it's apparently not that I am user 24601 with email address
TheStu.IsAwesome@Awesomesauce.com.
