I don't think the firewall is an issue because I'm running other games without a problem. But how do I double-check to make sure? If I did, that would mean I would have two ethernet plugs, right? I don't have two ethernet plugs. Yeah, but honestly that's quite a pain. I have to look up and memorize a number that could change each day. Also, I'm going to be hosting a tournament at a local con in a few weeks, and I would REALLY prefer to get this simple and automatic method working.

If other games are working than there probably isnt a problem. Usually what happens is that if you alt tab after trying to find a game there is a windows firewall dialog for the game asking for an exception.

You can also check if the firewall is running by going into Control Panel -> Action Centre (7+) or Security Centre (XP, Vista) Thats one example of you two physical ethernet plugs in the computer but its also possible to have virtual network adapters. Either use run or use the search (vista+) to start ncpa.cpl and have a look at how many network connections are listed. Yeah automatic method would be easier although I would actually recommend hosting UT on a dedicated server with a static IP address. Can you tell me what version of windows you are running to make it easier for me to help you.

Two of the machines are running Windows 7, and two of the machines are running Windows XP.
As nice as a dedicated server sounds, with only four machines I don't want to sacrifice a computer just to gain a relatively slight increase in performance.

Did some more testing today, found some odd results. When I ran the game on my regular computer (which I will NOT be taking to the tournament) all the other machines could see that game, and they connected just fine. A little later I tried again without using my regular computer, and they again could not see servers on the other computers.
But my regular computer is using the same install as the others, and I have no memory of ever changing any network settings in the game.

Fair enough even though it should run fine on anything you can easily get your hands on. That does sound odd to me, nothing springs to mind just yet apart from what I suggested previously.

Uhg. I found the problem. It turns out it was in the firewall after all.
In windows 7, I did a search from the start menu for "firewall" and I found the list of programs that are blocked or allowed through the firewall.
On that list, Unreal Tournament appeared multiple times, (on one of the machines it appeared four times, WTF?!) and some of the entries had odd allowances, like allowed on public networks but not private. I set them all up to be allowed and now things are working.

Good to here you got it working, forgot about the pain of public vs private networks, I personally make my life even more fun by running domain networks but that's just me and I wouldn't recommend it.