While there are specifics in mechanics and structure of NSMB that makes it NSMB, I think for the grand majority of people, making the graphics look nicer, swapping in new level mechanics and themes, and having a newer and more exciting soundtrack would be enough to get away from the NSMB stink. But of course the next game should do more than that. Does Mario have any new moves? What do the power ups look like? Do they retain the same world map progression, or do they try something else? The progression from 1 to 3 to World featured new mechanics for Mario, new powers, and different iterations of game progression from strictly linear to a more open map. For a subsequent 2D Mario to feel truly "new," it should follow in that lineage.