Check Call Status to make sure the user is not already logged into voice mail.
I have had customers that use Auto Hold, and whilst listening to a message another call comes to the phone and they just press the other CA and put the VM on hold. Then they want to log in to VM, but they cannot because they are already logged in.