A simple solution I found was to simply sign the old email out of iMessage and sign back in with the new email. Step by step:
On your iPhone, go to Settings
Touch "Messages"
Touch "Receive At"
Touch the Apple ID at the top, and a window will pop up. Touch "Sign out"
Touch "Add Another Email"
Enter the email/Apple ID you want associated with iMessage, enter your password, touch "Sign In"
An iMessage note comes up asking which email you want to use. Touch your email address, and then touch "Next" in the top right corner. The new email should be set.
This worked for me -- I hope it helps someone else.