both times when i got a new iphone, the iphone voicemail wasn't set up. it's not supposed to be, because they wipe your account's voicemail to set up for the iphone voicemail. (i'm guessing because it's a different setup for it to be able to do "visual voicemail" but i don't know.) the instructions say you should go to the phone section, click on the "voicemail" button in the lower right, and it would walk you through the steps to set it up. except i couldn't click on it like the other buttons on that row, and if i did get it clicked on nothing would ever happen.
i think this problem occurs when you aren't a new at&t customer? or maybe it's a smaller subset -- you aren't a new customer and aren't using the default voicemail passcode (the last 7 digits of your phone number). with both of my iphones, i eventually logged into the at&t website and went to the "phone/device" tab and hit the "reset voicemail pin" text. that resets the voicemail pin to the default, and sends a text message to the phone saying so. once i got the text message, clicking on the voicemail tab worked just fine and i was able to complete the process of setting up my voicemail.
it appears the voicemail passcode is expected to be the default 7 digits by the iphone software for doing the voicemail setup, but the voicemail reset at&t is doing for the iphone isn't resetting your voicemail passcode. and it doesn't appear to be documented by at&t that i saw.