Panel De Pon
It all started in Japan with a game called Paneru De Pon (or "Panel De Pon", in semi-English) on the Super Famicom (the "Super NES" in Japan). At first glance, Panel De Pon appears to be a "girl game" because of the fairies and colors, but behind the sugary-sweet façade lies one heck of a puzzle game. At least, it was good enough for Nintendo to bring it to the states 10 months later. But, similar to the way that Super Mario Bros. 2 was created, Nintendo decided to change the fairies and enemies into characters and enemies from Super Mario World 2: Yoshi's Island. The result was Tetris Attack.
Even though Yoshi hosted the panel-plopping puzzle game, it was still called Tetris Attack. So, unlike Super Mario Bros. 2, Nintendo probably wasn't intent on creating a new Mario game, but rather a new member of the Tetris family. This was a smart marketing strategy on Nintendo's part; the Tetris name plus new Mario characters fresh from Yoshi's Island equals a game that appeals to both Tetris and Mario/Yoshi fans.
Japan's version of Tetris Attack is called Yoshi's Panepon, released over the Satellaview. The identical copyright dates and the same English/Japanese language selection option in the Options mode leads us to believe that Tetris Attack and Yoshi's Panepon were made at the same time.
Going from Japanese to English, more than just the characters were changed, of course. Here's a comparison of Panel De Pon to Tetris Attack.
Related games mini-timeline