Timing errors after rerunning the design

Run a seed sweep on the original, or the new one, and see what the variation is. (Tools -> Design Space Explorer -> Effort Level = Seed Sweep). All designs have a random variation that you need to work within. Look at the following for more info:

http://www.alterawiki.com/wiki/the_quartus_ii_fitter_and_seed_sweeps

If your design has variation where it sometimes makes timing and sometimes doesn't, you'll want to work on improving the overall timing. The first place to start is Tools -> Advisor -> Timing Optimization Advisor, which will show a lot of Quartus settings that can improve performance.