Unless there is a significant delay in sending verification emails when updating your Stack Exchange email address (read: +4 hours), I think the verification email sending is bugged.
- Go to your profile and email settings page: https://stackoverflow.com/users/email/settings/current
- enter your new email address and hit Save
- make sure the "verify your email address" message appears (visual confirmation that the change request has been received - refreshing the page should show your new, unverified email address too)
The email hasn't come through and I've checked my Spam folder (and my trash folder just in case). I've also tried using the "Resend verification" link.