Update! I have successfully restored my Cisco 675 router!
I was pretty sure that when Qwest said my router was dead that they were just trying to get out of telling me how to fix it. And I understand that; hand-holding potentially thousands of users through the process would cost a fortune, support-wise. But insisting that the user must spend $300+ on hardware they already own seems to be crossing a line. So if you have a Cisco 675 (or 678 or any of the other 6xx'es), take heart: it is always possible to clear out the router, install new CBOS software, and set it all back up again. Don't let Qwest convince you it's an unfixable situation.
How to erase and re-install your Cisco 600-series router's software. I don't recommend doing this unless you have to, of course. There are a bunch of additional set-up steps to get your router re-trained. A Qwest technician was nice enough to walk me through the rest of the set-up after I did this unsupported step, because they have a script they can read from for set-up. (I still think the guy I spoke with was being nice because I sounded like I knew what I was doing, so either project an air of confidence, or tell them that another Qwest techie sent you to that Cisco page. :) Also note that you'll need another way to connect to the Internet (dial-up modem, or just take a floppy disk to work) to download the image.
The question of the summer: Will this eliminate my problems with the Code Red worm? I was one of the unlucky ones, where the advice that seemed to be helping others (disable the maintenance web server, assign it to a new port) wasn't working. Supposedly upgrading to v2.4.1 of the CBOS software would have helped, but it didn't the first time I tried-- but I didn't do a complete erase and re-install that time. Maybe, just maybe, the hole has finally been plugged. If I don't have to power cycle over the next week, that's a good sign that this procedure could help others with the same affliction. (It could also mean that the worm has gone dormant, as it is supposedly programmed to do by a certain date, in which case I might still be vulnerable when it comes back.) Stay tuned!
P.S. As of yesterday, Qwest has upgraded their phone tree to play an entire Dido album instead of that gawd-awful 30-second Muzak loop they used to have. Every 60 seconds, a recorded voice reminds you that you can also get tech support by email, but it's still better than before. They also no longer tell you that the wait is 90 minutes, just "in excess of 15 minutes."
I have a great deal of sympathy for the Qwest techies. They've had to put up with a lot because of this worm. So be nice if/when you call them.
P.P.S. I wrote out the set-up instructions for myself, and I'd be willing to share, but keep in mind that different ISPs and providers do this quite differently. I'm a Qwest.net customer on a Qwest ADSL line, with static IPs in routing mode. Dynamic IPs and/or bridging mode are outside of my support range. :P