I'm actually experiencing very similar problems with the Cyclone V. I have a number of designs that I've used for years on Cyclone III and Cyclone IV devices without any problems, and am now finding it impossible to make timing when creating an almost identical design on a Cyclone V.
I've spent some time looking at the timequest reports and the big difference between the older devices and the V seems to be the reported clock delay in the timing path.
For example, on both Cyclone III and Cyclone IV devices I typically see clock delays on the order of 0.2 to 0.3ns. On the Cyclone V the clock delay reported by timequest is more like 4.7ns. This is for the same portion of the design using the same clocks and constraints as the earlier designs.
I suspect that the source of the problem is a difference between the newer Altera PLL and the older ALTPLL. On the older PLL the clocks were generated such that the clock distributed on the global clock network was seen at roughly 0 delay, but the new PLL is introducing a long delay, at least from the perspective of timequest.
Any suggestions for improving this clock delay would be greatly appreciated!