Ouch. The game runs on a 200ms loop, so it's possible that it was not the networking that was the problem. If it's networking, you'd be seeing a tiny (WAIT) message popping up next to the other players' name a couple of times per second, if you are the host. Although, that could be an underpowered CPU on the other end, too. If you're running the host on a single core that is less than 2.4GHz or so, depending on your type of CPU that can cause some lag. With a newer Core 2 Duo or Atom or similar, the processor architectures are better and so the clock speed requirements are lower. With older P4s or similar, often those with the same clock speed still perform worse.
I'm not saying this is a CPU thing on either end, but it bears noting since I know nothing about the sort of computers being used to run the game in question. It might also be that you are having a lot of packet loss for some reason, or one of the players has insufficient bandwidth. Background downloads, other games being played over the same Internet connection, unreliable wireless connections, or the host of the game also trying to host voice chat have all been problems for various people in the past. With just two people it should do well on even a fairly slow broadband connection, though, unless something else is eating up bandwidth on one of the networks.
Over a standard cable connection (400kbps up), you should be able to host a four player game or more without any noticeable lag. When it scales down from there, it depends on the size of the game in terms of planets, what exactly is going on in the game at the time, how many players there are, etc. But if it's very early in the actual game itself, it shouldn't be an issue. As I mentioned before, though, AI War does have more data to send than your typical FPS or other similar game.
Hope that helps, that's all I can say for the moment, not knowing more about the specific setup here (upload speed, computer specs, etc).
