Unless you back up regularly, you may be in trouble. How did you erase the contacts? Sounds like operator error.
That's is what I was thinking. I went ahead to try this out by deleting a contact then syncing. Once it began to sync, it asked if I wanted to modify the Address Book (to delete the contact), I allowed it and it erased it.
So now, I have to restore my Address Book so that I can add the contact back again.
This may be a long shot and I have not tried it, but have you tried her old SIM card in the previous phone to see if she had listed her contacts on to the SIM card. You may have to enter it manually, but it sure beats getting "the look" from the wife.
If you do somehow get the contacts back, remember to back up the Address Book on the iMac. Just highlight all the contacts>File>Export vCard.