Thawing a parameter only means that Sherpa will vary it during the fit, but there's no guarantee that the fitting method picked must always lead to a better value than the one with which you started. If you mark many parameters as thawed, it is certainly possible (depending on the fitting algorithm used) that the improvement in the fitting statistic can end up being almost wholly due to a change in parameter A, and variations in parameter B end up having almost no impact. In such cases, Sherpa will leave parameter B at its original value.

On the other hand, when parameter A is frozen, then improvements in the fitting statistic can only be due to parameter B. Therefore Sherpa will eventually settle on some better value. In essence, you end up with a parameter space that is easier to explore and so it is easier to find a better value of parameter B.

If you really need to do a simultaneous fit on all the parameters at once, you could also try different fitting methods (simplex, Powell, Monte Carlo, etc.) and see if you get different results. Those methods are probably going to be slower, but exploring parameter space in a different fashion might also lead you to fits that Levenberg-Marquardt missed.