É o LagacyExchangeDN que está mudando. Encontre o antigo LagacyExchangeDN para o usuário no arquivo de registro do AddressBook abaixo, procure o usuário lá:
C:\Program Files\Microsoft\Exchange Server\V14\Logging\AddressBook Service
Você deve encontrar algo como:
/O=MyDomain/OU=First Administrative Group/cn=Recipients/cn=username
A linha inteira lá parece:
2013-04-12T12:18:49.363Z,9,0,/O=MyDomain/OU=First Administrative Group/cn=Recipients/cn=username,,192.168.1.157,servername,ncacn_ip_tcp,GetNewDSA,,5,Self,,Kerberos,
Copie a parte direita de lá.
Em seguida, abra ADSIEdit
e encontre seu usuário, abra as propriedades e vá para 'lagacyExchangeDN', clique em editar e substitua tudo pelo copiado do arquivo de registro.
Você também pode procurar no arquivo NK2 do usuário, onde você tem o erro, que lagacyExchangeDN está usando. Abra o arquivo NK2 apenas com o bloco de notas ou qualquer editor.