networkwise,
Let me guess it is not that people are able to find them in the directory as you changed the user description which is how they are found. The problem is that when they select someone it is playing the old users directory name instead.
The easiest way is to delete the mailbox and recreate it, as long as it isn't used in a Call Routing Announcement somewhere. If you don't want to do that then just have the user re-record the Directory Name along with the normal greeting.
Thanks,
TE