Can they reach their voice mail from the inside just fine?
Have you had those users do the same thing in front of you to make sure they're not fat-fingering the * and pressing 0 instead?
The only thing I can think of is that the tone isn't getting sent from their phone properly, but I'm more inclined to go with the fat-finger option instead having dealt with similar issues myself.