- Go to Central Administration->Manage Service Applications.
- Go to your User Profile Service Application
- Go to Manage User Properties
- Scroll down to Work email (under the Contact Information Section)
- Edit Work email
- Remove the existing Property Mapping for Synchronization mappings. They were inexplicably set to proxyAddresses (aCSPolicyName).
- Add new mapping to the mail attribute
- Start a Profile Sync
- Save and OK
It looks like just a simple profile sync would not work. You actually have to update the email addresses of each user and then do a sync. Argh!