Problem with SDRAM Timing

I wonder if you constrained your design in a way, that defines the complete SDRAM timing. Probably you didn't.

But anyway, the timing driven place and route process wouldn't modify the timing more than selecting between available alternatives. It will not add additional delay elements or assign fast input- or output registers where they are needed. It will at best (if constrained completely) report, that the timing isn't met, if it's limited means of correction are exhausted.

In other words, apart from constraining the design, timing adjustments may be necessary. For existing SDRAM reference designs, a lot of different measures have been suggested, including defining phase shifts for individual PLL clocks.