State machine unstable

This sounds very much like a timing problem or problem with asynchronous logic somewhere. Do you have proper timing specs? Do you have some logic that is not synchronised to the system clock.

If you have asynchronous logic you are luck to get the fitter to give you a placement that doesnt violate some timing relationship. The seed value for the fitter changes on every change on source code (ANY chance completly changes the seed) or fitter seed (set via the project settings).

Are all signals synchronous to the main clock? are there any paths that you havent synchronised?