Do you have an voice mail account assigned - Settings - Voicemail Settings. Normally 666
On 3CX dashboard - in the pabx status does system status have a green tick. If not if you click on system extensions, you maybe able to work out the issue
The problem was that the customer had maxed out the storage on the 3cx. Once I changed the voicemail settings to delete messages older than 30 days it opened up storage.
Unfortunately, a lot of people simply do not delete messages. In some cases, they do need to be kept (possible legal reasons?), but most users just can't be bothered.