This issue is now fixed, and since there has been no answers here, I will add an answer here in case the question is found in future searches.
I ultimately fixed this error by stopping the print spooler service (as a temporary measure).
It looks like the reading of Performance counters actually needs to enumerate the printers on the system (confirmed by a WinDbg dump of a hanging process, where I can see in the stack trace that winspool is enumerating printers, and is stuck in a network call). This was what was actually failing on the system (and sure enough, opening the “Devices and printers” window also hung). It baffles me that a printer/network issue can actually make the performance counters go down. One would think that there was some sort of fail-safe built in for such a case.
What I am guessing, is that this is cause by a bad printer/driver on the network. I haven’t re-enabled printing on the affected systems yet, since we are hunting for the bad printer.