In any event, if we're talking about resetting the passwords on Cisco switches and routers that are physically accessible, then we're talking about a much, much smaller problem. It takes a few minutes to powercycle a Cisco router or switch, break the boot, change the configuration register (0x2142), reboot the switch and restore the configuration (don't forget to reset the confreg!). I could probably write an expect script to do just that in 20 minutes. Multiply the time required to either do it manually or run a script by the number of switches and routers affected, and you have an estimate of the hours required to undo the damage. My guess would be that with a few knowledgeable folks with laptops and a brief set of instructions, the whole network could be "fixed" in a matter of a day or so. There would be downtime, of course, but it shouldn't be terribly significant.
As to the claims that he might have installed a back door into the system, I can't speculate. There are too many unknowns, and apparently too many clueless people talking to the press to get any real idea of what that might mean. And the claims of him installing a "tracing system to monitor communications related to his personnel case", well, that could be as simple as a keylogger or a SNORT box in the right place, or as complex as custom code running on a server somewhere. My guess is the former.
Granted, there are a lot of assumptions leading me to the conclusion that city officials are playing Chicken Little, but based on everything I've read so far, they're certainly making a mountain out of a molehill. Heck, I'd fly out there and fix the whole thing myself for only $500,000. What a bargain!