Sometimes the changes do not propagate to the web app. Go to the hidden user list and verify the email address is not correct:
..delete the user in question. Now to pull that user down again, you must add them to a group or grant permissions (You can delete those permissions immediately)
You should then see their email update in the hidden user list and people picker. Kind of a hack but it works for me when emails don't sync in my site.
Another thing that could be helpful (although I haven't tested this in a couple years). Is to view the UPA DBs. You can then run the delete command which will only delete the sync info, fire up User Profile to SharePoint Full Synchronization job again, and that should fix your sync issue:
Stsadm.exe –o sync –listolddatabases 0
Stsadm.exe –o sync –deleteolddatabases 0