Dan231,
More than likely the voicemail box was corrupted at some point or it is not an associated mailbox. Are the extensions for the mailbox and the phone the same, if so it is corrupted and it would be best to delete it and create a new one. If they are not then the phone's extension may be associated with a hunt group since you can assign it to another phone.
Thanks,
TE