Although efficient algorithms are available to sort signed permutations with reversals in a most parsimonious way, little is known about the corresponding counting problem, namely obtaining the number of most parsimonious sorting scenarios of a given signed permutation. This counting problem is conjectured to be #P-complete, and our current research focuses on finding an FPRAS (Fully Polynomial Randomized Approximation Scheme) algorithm. Such FPRAS algorithms usually apply a quickly mixing Markov chain, and the number of solutions are approximated from the samples of the chain. In this talk I will prove that the commonly used strategy for building Markov chains yields a slowly mixing Markov chain. I will also present a novel approach. Although we couldn't prove that the mixing is always fast, we couldn't find a counterexample so far, and the implemented method seems quick on biological data.