I had this idea a while back that to my surprise is already being used in Super Paper Mario. The character-swapping side-scrolling gameplay though, not the story...
The story consisted of Princess Peach finally installing a security system run by a super computer in her castle so Bowser's attempts at kidnapping her would be futile. Angered, Bowser hires a team of hackers to plant a virus into the sercurity system and shut it off without Peach's knowing. One day, when Princess Peach is having a party with Mario, Luigi, Toad, and Yoshi, Bowser crashes the party and grabs ahold of the princess. However, it turns out a glitch in the virus caused the security system to malfunction instead of turn off. The malfunction no longer makes it so intruders cannot get in, but now they cannot get out. As a result, the five characters are held hostage in the Princess's Castle by the damaged super computer. Mario, Luigi, Peach, Toad, Yoshi, and Bowser have to help each other destroy the computer and end chaos.
It would have been like a side-scrolling RPG where you were able to swap characters and each would have a different ability (Luigi jumps highest, Toad can go into tight spots, Peach's umbrella allows her to jump from high places). The final boss would of course be the Super Computer CPU, armed with tons of its own weapons.