VHDL "Quantum" bug

This sounds like some sort of timing problem - changing the output will change the fit seed and re-route the design, which may now mean that a route that previously failed is a different length that now works.

Do you have timing constraints for the design? How are you using a 1MHz clock? is it logic generated? these are notorious for creating timing problems. Have you synchronised all asynchronous inputs properly?