We are getting the following message "Design requires adding a large amount of routing delay".

​The paths in question where crossing clock domains. The clocks are derived from a single PLL but are asynchronous (25 Mhz and 8 Mhz) but the tools were treating them as synchronous, and trying to meet a hold because of that. A timing constraint was added to make the clocks asynchronous, and that solved the issue.