Another thing that could explain this is if you use large on-chip memories it might be hindering the placement if the memory is getting spread all over the place.
Normally when I perform timing analysis I normally start by double clicking the "Report top failing paths" macro. Often when you have some paths that fail by a large margin it can have a negative impact on many other paths in your design so that's why I start with the biggies first.
Once the paths are listed out I find the one with the most negative slack (it's in red) and right click it and select report timing and use the default settings to report the timing. It'll show you the clock and data paths so I normally drill down to the data path and look at all the incremental delays and try to figure what portion of my design would contribute to it.
All this said.... Also run "Report Unconstrained Paths" diagnostic since it'll tell you if you lack constraints. If you lack I/O constraints then that'll could have a huge impact on your Fmax.