Holy crap that's a good router
So my router problems came back mysteriously, and disappeared just as mysteriously several days later. I'm still not sure what the problem was, but in the meantime I decided I had spent enough of my time trying to diagnose the problem and bought a DLink DIR-655. The router still requires a lot of reboots during configuration, but not nearly as much as my original one. However, this is rock solid, and fast. I couldn't believe my eyes while I'm on the phone (using VoIP through the Internet) and watching a 435MB download (Visual Studio SP1) clicking off about 1MB/sec, which is nearly my rated download speed through Verizon FIOS.
Oh, and I was also connected to work at the time. Also, I haven't had a single unscheduled reboot since setting it up.