We consider systems undergoing very-low-temperature solid-solid transitions associated with minima of similar energy but different symmetry, and separated by a high potential barrier. In such cases the well-known "broken-ergodicity" problem is often difficult to overcome, even using the most advanced Monte Carlo (MC) techniques, including the replica exchange method (REM). The methodology that we develop in this paper is suitable for the above specified cases and is numerically accurate and efficient. It is based on a new MC move implemented within the REM framework, in which trial points are generated analytically using an auxiliary harmonic superposition system that mimics well the true system at low temperatures. Due to the new move, the low-temperature random walks are able to frequently switch the relevant potential energy funnels leading to an efficient sampling. Numerically accurate results are obtained for a number of Lennard-Jones clusters, including those that have so far been treated only by the harmonic superposition approximation (HSA). The latter is believed to provide good estimates for low-temperature equilibrium properties but is manifestly uncontrollable and is difficult to validate. The present results provide a good test for the HSA and demonstrate its reliability, particularly for estimation of the solid-solid transition temperatures in most cases considered.