Why was the gameplay of Super Mario Bros. 2 so different?

I wouldn't be surprised if this gets closed, but I'll do my best to answer anyway as I happen to know the answer.

The original Super Mario Bros. 2 that was released in Japan is known as The Lost Levels in America and wasn't released until 1993 as part of Super Mario All Stars (a great game in and of itself). When Nintendo of America got a hold of the Japanese version of Super Mario Bros. 2 they found the game to be too hard. According to Takashi Tezuka and Shigeru Miyamoto, this was actually the goal of the game, however NoA cancled the stateside release as a result.

Since The Lost Levels wasn't to be released in America and Super Mario Brothers 3 was about to be released in Japan, Nintendo of America singled out a different game to take the place of Super Mario Brothers 2. That game was Yume Kōjō: Doki Doki Panic. Since it featured 4 different protagonists with varying stats, Toadstool and Toad were added to Mario and Luigi. Its also worth noting that this is the first game to feature Luigi as being taller than Mario because the character he was based on (Mama) was noticable taller than the character Mario was based on (Brother). The result is what is commonly known as Super Mario Brothers 2.

Here is a paraphrased history behind the design of Super Mario Bros. 2 from an article on Wired.com by Chris Kohler.

Kensuke Tanabe, the director of Super Mario Bros. 2 himself, explained why the design was so different at the 2011 Game Developers Conference. The concept came from a prototype that featured vertical scrolling as opposed to the traditional horizontal scrolling. The player would be able to pick up items, pile them up, and then climb higher.

Shigeru Miyamoto (the creator of Mario) hired Tanabe to explore the new gameplay idea some more. Neither of them liked the concept; single-player mode wasn't fun, and there were technical limitations of the NES that hindered their team from creating a polished game. Miyamoto suggested that the game be more "Mario-like," and the sequel released in Japan became known as Doki Doki Panic.

Doki Doki Panic was also part of a deal between Nintendo and Fuji as a tie-in product for a media-technology expo. The expo's mascots were the main characters of the game. The game was a big hit in Japan on the Famicom Disk System, a peripheral that was not released in North America. Consequently, the game was ported to cartridge form instead (as were other games on the FDS).

When released in America, the Mario characters were switched with those in Doki Doki Panic to appeal to Westerners (since Mario was popular). The music and artwork of Doki Doki Panic also fit with the Mario feel since the Nintendo team developed the game. Some elements of the original prototype carried over into the final Super Mario Bros. 2 game in North America. Picking up blocks evolved into picking vegetables out of the ground, and picking up the other player turned into picking up enemy characters.

Super Mario Bros. 2 was then eventually brought back to Japan and titled as Super Mario USA because of the changes and enhancements that were made when it was converted for U.S. audiences.

• Source: http://www.wired.com/gamelife/2011/04/super-mario-bros-2/