An update for posterity's sake:
I received a new ethernet board from the seller only to find that the SAME exact pins were solder bridged.
I plugged it into my MEGA, uploaded the DHCP example sketch and it connected immediately. I uploaded the Teleduino DHCP sketch and that also connected immediately and has been running for about 18 hours with no issues.
I have no explanation for this other than the bridged pins must be OK to be bridge and that my card must have had a separate issue.
Or...aliens.