We have identified seven red supergiants (RSGs) in the Large Magellanic Cloud (LMC) and four RSGs in the Small Magellanic Cloud (SMC), all of which have spectral types that are considerably later than the average type observed in their parent galaxy. Using moderate-resolution optical spectrophotometry and the MARCS stellar atmosphere models, we determine their physical properties and place them on the H-R diagram for comparison with the predictions of current stellar evolutionary tracks. The radial velocities of these stars suggest that they are likely all members of the Clouds rather than foreground dwarfs or halo giants. Their locations in the H-R diagram also show us that those stars are cooler than the current evolutionary tracks allow, appearing to the right of the Hayashi limit, a region in which stars are no longer in hydrodynamic equilibrium. These stars exhibit considerable variability in their V magnitudes, and three of these stars also show changes in their effective temperatures (and spectral types) on the time-scales of months. One of these stars, [M2002] SMC 055188, was caught in an M4.5 I state, as late as that seen in HV 11423 at its recent extreme: considerable later, and cooler, than any other supergiant in the SMC. In addition, we find evidence of variable extinction due to circumstellar dust and changes in the stars luminosities, also consistent with our recent findings for HV 11423 - when these stars are hotter they are also dustier and more luminous. We suggest that these stars have unusual properties because they are in an unstable (and short-lived) evolutionary phase.