My theory was right, and I've got the Pix operational now. I'll try to explain the issue. Hold tight.
A network is a bunch of computers, all sharing a cable. And they need to talk to each other. To do that, each one needs to know where the others are. This is done using ARP, Address Resolution Protocol.
They need to work out which IP address (like 10.23.34.45) corresponds to which hardware address (like B8:27:EB:C3:2A:13). So they're forever exchanging this information, so that everyone knows where everyone else is.
Then I put a bunch of computers behind a firewall. The computers not behind the firewall, are still sending out ARP packets, but what they get back from the computers behind the firewall, is the ip address that the firewall presents to the outside world, and the hardware address of the firewall.
So, what I did, was I took out the Sonicwall, and inserted the Pix. That worked fine for the computers in my network, but ...
I have a second firewall, it stands right in front of my internet connection, filtering everything. And it had the hardware address of the Sonicwall in its ARP memory. When I switched to the Pix, it was still sending packets to the Sonicwall, which was no longer there. So that meant that everyone outside my network wasn't able to contact the computers behind the Pix that replaced the Sonicwall.
You'd think that the second firewall would have asked for new ARP information. But it doesn't, not immediately. Not for four hours, actually - the ARP cache is 14400 seconds on the Pix.
So, how to deal with this? It's very easy. I could have switched the second Pix off and on again, but I don't have to be so drastic. CLEAR ARP does the trick.