I had the client go through the following steps and it skips Press 2 to record your name in the directory. There is no way to record the new name. I'm not sure if resetting the phone will resolve the issue or not.
After opening your mailbox:
Press 4 for Setup options.
Press 3 for Personal settings.
Press 2 to record your name in the directory (you will hear the current name).
At the tone, record your greeting.
Listen to voice prompt.