Female employees get married and change their last name. DL might change their display name. I have been asked few questions about this change like "I still see the old name in Exchange System Manager", "Outlook doesn’t reflect the name change". I would do the following things in order.
a) Change the User’s Name in local domain controller in the local site. Make sure you also ADD new Email address accordingly, but Do NOT delete any existing email addresses. Most probably user wants to be reached with new and old email addresses for a period of time.
b) Initiate the Active Directory Replication manually if the change is made in different site and "Exchange Recipient Update Server" is in different site. The point is get the change immediately to the site where "Recipient Update Service" resides and it can recognize the change right away.
c) If you don’t want to wait, manually initiate the update process by right click on corresponding "Recipient Update Service" & select "Update Now" in Exchange System Manager. (To get there, Open Exchange System Manager and go to Organization–>Recipients–>Recipient Update Service)
d) Wait for two minutes for Recipient Update service. Manually generate the Offline Address Book. Wait for another 5 minutes.
e) Initiate another manual AD replication between sites, if the user is in another site.
e) On affected User’s computers, create a new Outlook Profile to show new changed name. If not, Outlook will continue to show the old name, but sending mails will go with new display name.
f) As new Offline Address List is generated, it will get downloaded to user’s Outlook (give it a day) and show the correct name in the GAL or Outlook Address Book. Outlook users whose using online mode and OWA users will see the change immediately.
Anand, the Architect 
For me the problem was because the option “Use cached exchange mode” was enabled, once I disable\re-enable it, it starts displaying the correct new names.