Stratix III dev kit: factory design doesn't meet timing requirements - why?

The reference design did not meet timing when you compiled it, but it most certainly did when altera compiled it and provided the programming files. That means the design is capable of meeting timing, just not with the particular parameters you chose when compiling. Try changing the fitter effort, seed values, remove common clock pessimism on the timing analysis, run a seed sweep, tell it to compile for timing and not space, duplicate registers for increased timing, etc.. A lot of options can effect the outcome of the compilation, just play with them until you find a balance of compilation time and results.