Applying this fixed everything for me. I don't know what changed, but suspect it must have been something with my ISP - coincidentally around the time that my old cable modem died.This probably won't help the routing issue, but try running the
following commands at startup:
echo 1024 >/proc/sys/net/ipv4/neigh/default/gc_thresh1
echo 2048 >/proc/sys/net/ipv4/neigh/default/gc_thresh2
echo 4096 >/proc/sys/net/ipv4/neigh/default/gc_thresh3
That will increase your ARP cache (the neighbor table) to about 4
times it's normal size. If you open up a lot of connections at too
high a rate, your ARP table will overflow and you will basically get
a network shutdown. You might want to try running "ip neigh show" or
"arp -v" (same data, different net-tools) to see what you're ARP
table looks like. If you notice a lot of connections to a single
subnet, you may be getting DoSed by a bunch of NT boxes infected with
Code Red. Fits your timeline, and it is a known pain-in-the-ass
problem on broadband these days.
I don't know how to set these parameters so that they'll be remembered permanently - I've resorted to adding those commands to my /etc/rc.d/rc.local file (ugh).