I'd pick up the phone and call Apple and ask for help. In cases of public settings I've heard and seen when an Apple staffer makes a house call. Rare but if you don't ask Apple you may have lost a free visit.
Also why not try another router? Cheap!
Got an odd issue with an Airport Extreme Base Station I just connected to the in-house network at our small museum. If the Airport is up and running before two of the Macs on the network are booted up, they refuse to connect to the Internet, although both are connected to the network, can be "seen" and accessed by the other Macs on the network, can access the networked printrs, and insist, in the Networking preferences panel, to be connected to the Internet through their Ethernet ports.
Both are running OS 10.4.11, both are G4 Quicksilvers with 1.5 Gigs of RAM with 150 gig HDs. The G4 Dual 1.25 MDD Mac on the network, which is running OS 10.5.8 has no issues.
If I boot everybody up while the Airport is powered down, everything works swimmingly. If I then boot up the Airport while everyone is up and running, everything still runs just fine; everyone can log on and off the Internet.
Another interesting quirk. If the Airport is up and running and then one of the Qucksilvers is booted up and won't connect, the Mac can sort of be forced to connect by shutting it down waiting a minute or so and booting it up three or four times in a row.
Anyone have any suggestions about what the heck is going on? I have a feeling it's a problem with the Airport vs 10.4.11, and that upgrading everybody to 10.5 would do the trick, but we still need to access some Classic files on one of the machines.