Yeah, I am not sure what happened with my iPhone either. I was dialing regular voicemail, and all of a sudden I was able to access visual voicemail. No reset or anything. I think it has to register with the ATT network which takes a while like everything else.
Visual voicemail is truly remarkable. Such simple changes to voicemail, but awesome nonetheless.
checking visual voicemail (through the visual voicemail tab in the phone application) does not use minutes, it uses data. you'll notice that when you don't have an edge signal and you go to the visual voicemail tab, you get an error that states visual voicemail is unavailable, and your only option is to place a call to your voicemail box to retrieve your messages. you can listen to visual voicemail messages only when you have an edge signal since that's how they are downloaded for listening.
of course, when you make a call to check your voicemail messages, that is an actual phone call. but, iirc, these calls are noted as voicemail retrieval on my bill and are not deducted from my plan minutes (i'm with AT&T on an official iPhone plan)...