I would like to offer something completely different.
Picture this: "Super Mario Temporal" I'm thinking that the key innovation here would be the utilization of positional time effects. I see different spatial locations exhibiting different temporal coordinates within the same level. For example: Mario could walk down a hallway and stumble on a "time changeing zone" whereupon it's 500 years in the future, Bowser has taken over thsi zone you are attacked by mechanized goombas. I'd also like to see causality worked in say that, in our hypothetical, Mario could take another few steps, leave the zone, go back into the "present" moment get the level's star and Mario could go back to the "time changing zone" and would find a more peaceful world, as he prevented Bowser from taking over.
That's what I'd like to see gameplay-wise in a new Mario game. If it had a dark feel to it as well, that could be acceptable.