It's always possible that the cable is damaged. How is it run underground? Is it in some sort of conduit? Is there any possibility of pulling a new cable? There are devices that will test a cable to see if it is capable of supporting the data you want to pass, like the Fluke CableIQ, but they're pretty expensive and I don't know if there's anywhere you could rent one.

Oh, you might also try forcing speed and duplex settings.