It's all relative, I think.
Super Mario All-Stars is essentially a re-color of the old games. While it does add a save menu, the games are (more or less) intact. So it's a remake (and a compilation), and it's also great.
Legend of Zelda: Link's Awakening DX is a re-color of the old Gameboy Legend of Zelda: Link's Awakening. It adds a handful of new aspects but it's basically the same. So it's a remake.
Castlevania: The Adventure Rebirth is a completely new reimagining of the Castlevania Adventure Gameboy game. It's completely different in stages, colors, and game mechanics. It is still a remake, though.
So it seems that the term 'remake' is relative. It can be something as simple as "This was a NES game. Let's make it have SNES graphics with a richer color palette" and that's already good enough. You can, also, crank it up to 11 and make an entirely new game that's loosely based on the original, and it would still qualify as a remake.
You can also do a retro-remake. MegaMan 7 and MegaMan 8 in 8-Bit, for the PC, are NES-like "Remakes" of SNES and PSX titles. They're still remakes, though. It works both ways.