Same problem - iChat says all buddies are offline, even though I know they are online
I unsuccessfully tried to chat with my parents' brand new iMac from my one year old macbook - both running leopard. Very frustrating.
I was at their house when they got the iMac and tested iChat, but was only able to connect with Bonjour - and that was only after "allowing all incoming" in the firewall prefs. I thought that we couldn't connect the regular was because we were on the same wireless network. But now that I am home, we still can't connect over the internet.
I seem to remember ichat working with a friend's macbook, though (both with leopard). I might ask him what his settings are to see what we can come up with.