Changed UPN

Hi All,

We had changed UPN for one of the user. Now user can access all o365 services just fine.

User can even login to Lync but when other users try to search him using his email address it shows unknown and when they search him using UPN it shows fine.

is it the matter of Addressbook replication or how do we sort out this problem?

Thanks