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.