Hmmm, I thought they could do this for you. I know they have changed their voicemail system now, did you get the new one with the male and female voice?
I'd call them back and explain that it didn't work. I'm pretty sure they have changed things like this for a friend on 3.