Well, turns out that the firewall installation was not quite perfect.
The Southside, a part of our office that is not directly connected to the rest of our office, comes back to our wiring closet on fiber.
It was outside of the firewall loop, so they couldn't get anywhere, except to each other's machines. Printing was even an issue.
A missed step, and one that's not easily fixable. We could have given them all static IPs, and the printers too, and that would have worked. They would not be going out the firewall then, though.
Or we could take the firewall out, and wait for Brown's CIT department to come over/call and help us figure out a solution.
We took out the firewall, and now are awaiting Brown's bitching. Here's hoping we can solve this one pretty easily.