Clock network delay + internal cell delay > Minimum timing requirement

If you can't use a PLL, perhaps it would just happen to work out to invert the clock for the output registers to adjust the timing by a half period. You might then have to slow the output delay chain if the half period is too much.

Are you certain you have the I/O timing constrained correctly? You should use both maximum and minimum output delay constraints (preferred for either timing analyzer) or both tco and min tco (OK for the Classic Timing Analyzer). If you are just calculating the timing manually, you might have missed something.