We believe we've found it - the internet-facing NIC had a minor configuration change as well, as part of the upgrade. It was no longer explicitly being set in full duplex mode, and as it turns out it was coming up in half-duplex.
Now we play the waiting game to see whether we are right :-)
