Well, finally figured out the problem. My ISP (Adelphia) is dropping outgoing [SYN, ACK] tcp connection handshake packets that originate from port 80. As far as I can make out, no other ports are blocked; ftp, ssh etc all work and the web server works fine when running on another port (ex: 3245).
I had called their help desk at first but apparently the lower level analysts are not aware that adelphia blocks this way. What a waste of time...