After changing the email address I logged out of the App Store, iCloud, iMessage, and Facetime. I then logged back in using the new email address.
I did this on both my iPad and Phone, but it only seems to be the phone that keeps prompting for the password.
I doesn't prompt at any specific time, it just pops up at seemingly random times.
A search on the Internet hasn't turned up anything helpful.