Nos Usuários e Computadores do Active Directory, você precisa alterar os nomes dos usuários. Seus nomes estão listados na guia "Geral". Eu não tenho certeza se você pode até ter um 'no nome da conta, mas se você puder - e lá você muda isso na aba conta. Como você diz que eles precisam alterar o caminho do perfil deles, presumo que você possa ter um 'no nome da conta ...
Se você usa o Exchange, ele deve selecionar as alterações do AD, mas não faria mal entrar no Exchange e fazer as alterações no usuário também.
Quanto ao perfil, isso é uma solução fácil. Enquanto estiver logado em sua máquina como outro usuário (muito provavelmente você) renomeie seu perfil atual. O mais fácil é adicionar um sublinhado (_) na frente dele. Faça o logout e faça com que eles efetuem login com sua nova conta. Isso criará um novo perfil com o nome correto. Uma vez feito isso, faça com que eles saiam. Faça o login como você e copie o conteúdo do perfil antigo para o novo. Eu faria uma cópia em vez de me mover por precaução, para o caso de algo dar errado. Em caso afirmativo, você sempre pode desfazer todas as alterações, incluindo a remoção do sublinhado no perfil anterior.