You might want to check that the Care rep added Visual Voicemail to your wife's line. The easiest way to check is do a password reset and it will send a SMS Txt msg to the phone. Once this is done you should be all set. Visual voicemail needs to have a password set from the iPhone. This allows the iPhone to get the voicemail messages via the data plan. That's the reason that Visual Voicemail only works when you have the iPhone data plan.
Reset voicemail password from AT&T's automated system
1. Call 611 or 800-331-0500.
2. Enter the wireless number starting with area code.
3. Press 3 to get help with voicemail.
4. Press 3 to reset your VM password.
5. Enter the Billing Zip code for the account.
After a few seconds, iPhone will display "Password Incorrect - Enter Voicemail Password." Enter the last seven digits of the wireless phone number and tap OK.