If you dial an extension from the auto attendant and it replies "That was an invalid entry", then this is a good indication that the voicemail box no longer exists. There is an option in the TUI admin mailbox to add a new extension. Try adding it back.

There is a mailbox that has default settings, including the default code, for new mailboxes. It is not common but I have seen some cases where someone changes code for the default mailbox, which will change the default security code for all new and reset voicemail boxes. Fixing the default settings may be difficult and will probability require someone accessing the voicemail system using Toshiba software.