I had problems with this too but here's what I did. First, make sure you are on an AT&T tower with a decent signal. Next, try again. For some reason it seems sometimes it "times out". Finally, if all else fails, call AT&T and verify that voicemail is properly set up on your account. There are many reports of individuals with plans that were not set up properly during the widespread activation issues.