We consider systems undergoing very-low-temperature solid-solid transitions, exhibiting the well-known "broken-ergodicity" problem that is often so severe that even the replica exchange method converges too slowly. We propose an improvement of the latter, which consists of coupling the lower-temperature random walks to analytically generated random walks corresponding to an auxiliary harmonic superposition system. Numerically accurate results are obtained for several Lennard-Jones clusters, which have so far been treated only by the harmonic superposition approximation.