This is a bizarre problem. KNetworkManager for some reason cannot see my router on my wired ethernet connection, but can see the exact same router through a wireless USB adapter on the same PC. I've confirmed this isn't a hardware problem by using a Kubuntu 8.10 desktop CD, which successfully found the router through the wired connection (I'd disconnected the wireless adapter, it had no other way to see the router).

This happened after a reboot when my system had been up for some time, I presume an update installed at some point during that session broke it. The wired connection worked perfectly fine before. Disconnecting the wireless adapter has no effect, the wired connection still doesn't appear.