This usually happens because VM Notify can not find the voicemail file because you have in your extension setup the voicemail being deleted after email. This creates a race condition on the voicemail system and the email portion of app_voicemail deletes the new voicemail within milliseconds of it being left and we do not have the opportunity to grab the voicemail file and move it before it gets deleted. You need to disable voicemails being deleted on the extension after email.
This usually happens because you are using non FreePBX Distro and your voicemail configs are not setup correct. You need to follow these steps.
Go into the Voicemail Admin module in FreePBX under Settings Category.
Click on the Settings tab at the top
Scroll down to the extennotify section and make sure you add this string
/var/lib/asterisk/agi-bin/vmnotify-newvm.php |
Press the submit button when done.