When the app first opens the greetings screen, it should have asked you to Allow access to the Mic. If select don't allow, you have to manually allow it in you privacy settings:
Go to Settings
Select Privacy
Select Microphone
Scroll down to Voicemail and ensure the slider is set to on (green).