Make sure they (PC) have latest version of AIM.
Also, check your routers to insure they aren't blocking the ports iChat A/V uses. http://docs.info.apple.com/article.html?artnum=93208
Might double check on the router(s). Even if you don't have a stand-alone router, a lot of cable/dsl modems have a one built-in.
I, and they, are plugged directly into an ethernet cable.
both computers are plugged into the same cable? like a splitter?
No. I meant that neither of us are using a router. Both of our computers are plugged into our respective ethernet cables at our separate houses.