When you go in to edit/change the recorded message, doe it play for you what is already there? Can users change their VM messages and it works?
Sounds like possibly the SD card is corrupt. Might want to use Manager and default and re-create teh Card.