Callers are unable to leave voicemail

Is your voicemail box full?  Every voicemail box is limited to 100 total messages (the length of each message is not limited)

Does the voicemail box exist?  Sometimes a customer will create a step in a call menu to 'go to voicemail' but forget to actually create the virtual voicemail extension.  Double-check to make sure the box you are referencing exists in the extensions page.