Other things to consider are that this may be a power / bypassing issue or perhaps a simultaneous switching noise (SSN) issue and not a timing issue.
We had similar issues to yours - sometimes the design would work and then with seemingly trivial design changes it would stop working. In our case it looked like the FPGA was getting "reset" (all state machines, registers, etc. went to reset state) as a result of driving certain combination's of outputs - basically SSN issues.
SSN is more likely in QFP packages and there are some forums or web info on SSN with respect to Altera parts you can search for.
If there is noise on the power lines, or marginal bypassing, it's possible this could be effecting the operation.
Changes to the design effect the routing and placement which may put susceptible signals closer to problem areas.