After researching, this seems to be a more common problem than I had first thought. After a lot of reading, and a lot of experimentation, I've finally gotten voicemail functional again. When it is not operating, the VM light will be off on the front of the UC5xx unit and when you dial voicemail, you will not reach anything. The order of these steps are very important.

A user of a Cisco IP phone has both a PIN and a password. In Cisco Telephony terminology, the password is for accessing CUE (Cisco Unity Express-- a web-based configuration program generated on the UC500 device), and the PIN is needed for voicemail access.