There should not be drastic changes for Quartus. What happened might be some of the synthesis might not be recognized in Q16.0 and was enhance in Q16.1 onwards.
Can you attached your Quartus 16.0 design.qar here for us to duplicate?
PS: Please note that design.qar would be public here, let me know if you do not want it to be public.
I cant share the project files.
I tried different "dummy" projects, but could not recreate the issue, they were not big enough.
I wanted as a first step to clarify there werent any drastic changes to affect analysis & synthesis time, and if there were any similar cases you seen.