After 45 minutes on the phone with AT&T Wireless/Cingular and conversations with Vonage, I have determined that these two companies are incompetent and can not successfully route calls between each other’s networks.
Update: After threatening to cancel my service, I was informed by the customer care (yeah right) that my contract explicitly states that they can not guarantee interoperability with any other network, including the international phone network. Pretty interesting considering they are selling me phone service.