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?