The convergence of parallel tempering Monte Carlo simulations of the 38-atom Lennard-Jones cluster starting from the O-h, global minimum and from the C-5 nu, second-lowest-energy minimum is investigated. It is found that achieving convergence is appreciably more difficult, particularly at temperatures in the vicinity of the O-h -> C5(nu) transformation when starting from the C-5 nu structure. A strategy combining the Tsallis generalized ensemble and the parallel tempering algorithm is implemented and used to improve the convergence of the simulations in the vicinity of the O-h -> C-5 nu transformation.