The path that was failing was a hold timing path on register q1 in an instance of eth_dc_reg. I've spent some time on it and can't really figure out why the fitter isn't able to meet the hold timing requirement other than the timing constraints I've put in the SDC file are somewhat overkill. The instance that was failing was the "tx_start_dc_reg" instance inside of "eth_avalon_rxdma.v".
Anyway, I modified the logic slightly so that only one register output feeds the input the the failing register and it still fails.
Finally I just went into the Fitter Settings (Assignment->Settings->Fitter Settings) and changed the fitter seed from 3 to 4 and that fixed it. Quartus then did a completely different optimization and placement on the register feeding the failing register and it passed. For the moment I'm going to write this off unless it presents itself elsewhere in the future.
Jake