I've been doing some thinking, and New SMBW makes me think of Donkey Kong 94 (released on the Gameboy in 1994, for the uninformed). In DK94, they took the story from the arcade Donkey Kong and then gave Mario new moves (backflip, triple jump), put in more levels (after the first four,anyway) and added also some puzzle elements (carrying a key to the door, being able to place ladders and floors, etc..)
I'd been trying to place what this game made me think of whenever I start playing, and I think it's that.