First, a little background. A few days ago, a strange thing happened. One of my machines, a Linux box, stopped being able to make outbound TCP connections. What was even more strange about this, is that it could send out UDP/ICMP packets just fine, and all incoming connections were going fine.
Sounds odd, right?
Well, it gets more unusual. The machine in question (nexus.zyp.org) also acts as a firewall, and provides NAT for a handful of other machines. The machines behind nexus, when going through nexus, were perfectly capable of making outbound TCP connections. That threw a serious wrench in my guesses of what might be going wrong.
A few moments ago, a random thought hit me, and upon further investigation, solved the problem. A couple months ago, I started including support for ECN in the LInux kernels I built, because I'm planning on doing some testing with it, soon. Not a big deal, because my network initialization scripts disable it by default. Or, at least, they did. When I was updating my network scripts to set up NAT through this box, I typo'ed a line, and accidentally set the network scripts to enable ECN.
This was made more confusing because it wasn't enabled immediately, but upon my next reboot. Unfortunately, since this occurred in the network scripts, going back to a previous kernel didn't solve the problem, as it was having ECN enabled on it, too.
So, to sum up, my ISP is one of those that uses a broken router that harfs on ECN, and thus was having problems with my outgoing connections when it was enabled (Although, why things went through NAT fine still is a mystery to me). I've disabled ECN, and everything seems cool again. ;-)
 Network Address Translation. Basically, it allows the machines behind it to access the Internet, even though there is only a single Internet connection.
 Explicit Congestion Notification. A very good thing. . . in theory.