Aha, it's the iPhone. You need to have AT&T check that the visual voicemail feature has been completely removed from your account.
The visual voicemail that the iPhone uses is different from the voicemail system that other phones use (obviously), and causes stuff like that with other phones. Call AT&T back and let them know that you no longer have the iPhone and need your account updated.