The configuration had one NIC plugged into the local LAN and the other with a public IP address in the DMZ. A Kerio Control firewall protects the internal network.
My assumption was that he had accidentally enabled a firewall on the new system or that the public side NIC was bad, but I was wrong - the customer himself found the problem after thoroughly reviewing his configuration.
The actual problem was routing - when packets came IN to the public IP side, the system was trying to respond to them through the router on the internal NIC. From the Kerio Control firewall's point of view, here were responses to packets it had never seen coming in - quite naturally it wasn't going to let those through. The Ubuntu graphical network configuration tool has a simple check box that needed to be enabled on the LAN card. It says "Use this connection only for resources on its network". With that checked, response packets for the public IP would go out the same interface where they had come in, and the mail server could now receive mail.
The other way to configure this is to ONLY use the one local IP address and have the firewall forward appropriate ports inward. That's the way most systems are set up today; but you need to keep routing in mind when configuring multi-homed servers.
I don't know why I messed that. It had been a long day (I exhausted my cell phone battery twice that day and did the same thing to one of my wireless home phones!) and I was tired, but as we had tried switching cards (putting the public IP on the lan side and vice-versa), cables and switch ports, and the customer could not identify any local firewall, it HAD to be routing and I just didn't pursue it. Oh well: another day, another lesson learned.