Let's stipulate that it worked great on the problem they analyzed. That problem was really very simple. If they used a more appropriate technique, they could expand the domain of applicability significantly.

Like I said, I've used MCMC for loosely-structured inference problems (but more structured than the one treated in the paper). I was doing MAP estimation (i.e., maximizing the objective function), just as in the paper.

When speaking about my work, I was once asked "Why MCMC on such a hard problem if you're really just maximizing?" It's still a good question.