Using this setup, I can contact computers on my local network fine. However, when I attempt to contact computers on the public Internet, the device times out. I traced the packets going back and forward using Wireshark and the problem appears to be that the gateway is not responding to the W5100's ARP request.
I saved the ARP packet that the W5100 is sending and the ARP packet that my computer is sending and compared them. The only thing different is that it is not a timestamp, address, length or sequence number that the W5100 is sending a trailer at the end of the Ethernet II frame.
According to RFC 1122 - Requirements for Internet Hosts - Communication Layers, section 2.3.1, a trailer may only be used if both hosts have previously agreed to use them. I suspect that my gateway is not able to handle trailers and is ignoring the packet.
Is there a way to disable trailers in the W5100?
Here are the ARP packets that are sent by a computer on my network that is able to make Internet connections and the Arduino device. I have also provided a diff of the two packets. In the case of the packet that is sent by the computer, the gateway responds, in the case of the packet sent by the Arduino, the gateway does not respond. Note that I have changed the hardware addresses, but that's all.