Two independent replica-exchange molecular dynamics (REMD) simulations with an explicit water model were performed of the Trp-cage mini-protein. In the first REMD simulation, the replicas started from the native conformation, while in the second they started from a nonnative conformation. Initially, the first simulation yielded results qualitatively similar to those of two previously published REMD simulations: the protein appeared to be over-stabilized, with the predicted melting temperature 50-150K higher than the experimental value of 315K. However, as the first REMD simulation progressed, the protein unfolded at all temperatures. In our second REMD simulation, which starts from a nonnative conformation, there was no evidence of significant folding. Transitions from the unfolded to the folded state did not occur on the timescale of these simulations, despite the expected improvement in sampling of REMD over conventional molecular dynamics (MD) simulations. The combined 1.42 micros of simulation time was insufficient for REMD simulations with different starting structures to converge. Conventional MD simulations at a range of temperatures were also performed. In contrast to REMD, the conventional MD simulations provide an estimate of Tm in good agreement with experiment. Furthermore, the conventional MD is a fraction of the cost of REMD and continuous, realistic pathways of the unfolding process at atomic resolution are obtained.