Rebuild the offline address book after you have checked all of the entries in AD for the user are correct (check all the tabs)
In outlook (the name at the top after mailbox) this only changes if you close outlook, open the mail icon in control panel and change the exchange username. (the bit where you specify the exchange server and the username and can click the check name box). I believe this is the only way to reset it, certainly on the local machine.
I had a similar problem recently and this resolved it.
If the cache is new (having deleted the file) then I would imagine the address book still has old details.
cheers
Andy