I have been a 2degrees customer for three and a half years and have used voicemail numerous times over that period. Yesterday I called voicemail to pick up a message and received an automated prompt telling me that I haven't used voicemail before and I should therefore set up a personal greeting.

I don't know how 2degrees have managed to lose my voicemail greeting, but you might want to check your own greeting in case the problem is widespread.