I did try a software upgrade a month or so ago as a troubleshooting step for voicemail to email not working and had to roll it back as we didn't have software assurance and the system freaked out about licenses. Could be related... I'll try a restore next week and see what happens as I'm out of town tomorrow and over the weekend.
Side note, if I restore, am I able to upload any voicemail files that exist now that were added after the backup I restore from, or will that break things?
Funny enough, that's the exact situation I ran into. I think the upgrade does something to the existing partition (even though it shouldn't). There's a procedure to just restore the embedded VM out on KMS which worked for me. I wasn't able to figure out a way to restore the messages that were there but not showing as new. I just extracted the raw audio files, converted them in Audacity, and gave them to the customer.