Over time, video games have become easier and easier. There are a lot of factors that contribute to this. One of the most basic is the size of games over time. Games like Zork and King's Quest I can be finished in less than half an hour. (I understand Zork can be finished in less than a minute, since it's a text based game.) The first Mario can be beaten in five minutes. People want a return on investment, and a 5-minute game wouldn't be much of a payoff for 60$.
Since you can't make a game bigger on the NES, (there's only so much filespace, after all) you have to make them harder to make the game take more than half an hour. You can play Mario for hours because it's very hard.
Nowadays, you can make a game take as long as you want by adding more levels. File space isn't infinite, but it's so much more than earlier generations that it allows a whole new type of game design. Super Mario World didn't have to be hard to entertain for hours; only the most ambitious speed-runners could finish it in less than half an hour, and there's no way a first time player could stumble on to the absurd path necessary to finish that fast.
Anyway, I've been playing the REAL Mario 2 lately, (The Lost Levels) and I can understand why they didn't bring it to the US. It is really, really, really, EXTREMELY hard. (I've been playing it on the SNES Mario All-Stars, and that is actually an easier version than the original NES version.)