It really should say that the call cannot proceed because the caller id information is withheld and then just hang up, or direct the caller to contact their own telco for information on unblocking it. It also may indicate that their is a fault when its actually the callers decision to withhold their number that is resulting in the call failing to go thru.

Perhaps you could make it a user recorded file from the voicemail configuration instead of a fixed system message? I would put something on it about how its rude to call someone with your number hidden and I see no reason to take the call from someone that won't identify themselves.