On the Spartan 3E Starter Board the signals A and B of the rotary shaft encoder are actually inverted!
This is not mentioned in the documentation, the figure found there is strongly misleading . At least the pullup resistors are mentioned, which can bring you on the right track.
Oh and remember to put a reset on your FSMs :o)

References: Spartan 3E Starter Board documentation