First off, what exactly is it that makes Mario kiddy? You didn't exactly define that in your post. You mention story, but story has changed very little in any Mario games.
Donkey Kong- Giant Gorilla has captured Pauline. Go save her.
Super Mario Bros.- Giant reptile has kidnapped Peach. Go save her.
Super Mario 64- Giant reptile has kidnapped Peach. Go Save her.
Super Mario Galaxy- Giant reptile has kidnapped Peach. Go save her.
NSMB Wii- Giant Reptile has captured Peach. Go save her.
Super Mario 3D Land- Giant Reptile has captured Peach. Go save her.
Of course, other Mario games have offered more story. In particular, the Mario RPG series has constantly offered very adult humor. Not adult in the sense of "I once knew a man from Nantucket", but adult in the sense of knowing in-jokes, self referential humor, and subtle jokes that would go over a child's head. Even Mario Galaxy had a somewhat somber story to it, if you spent the time in the library.
But as for the main story, it's changed very little. To be honest, the only change is in the subjective way which you described them. You say that Mario Bros "is the story of a plummer that needs to attack crabs and turtles and butterflies, with fireballs coming out of the wall to attack him." Well, Super Mario Sunshine is a story of a plumber crushing small animals underfoot, blasting enemies into walls with powerful streams of water, and RIPPING THE LIMBS OFF OF Squids who stand in his way. He does all of this in an effort to clear his name which has been besmirched by a shadowy imposter as part of a misguided quest to find his long lost mother.
You also mentioned color, but that seems unfair considering the differences in hardware. Naturally, the NES/Arcade systems of the time were limited in the amount of colors that could be easily replicated. Besides, I'm not sure what makes a color kiddy or not kiddy. Are bright primary colors only for children? Super Mario 64 has a whole level based on Rainbows and sunshine and is filled with color. I don't know what makes other games more kiddy in terms of their color palette.
As for why the mainline Mario series isn't a story with "real emotion" it's because that isn't what Nintendo wants it to be. Simple as that. Miyamoto in particular thrives on making games which are simple, accessible, and have great pick up and play value. Personally, this is what I'm looking for in a Mario game. Whether that's better or worse is subjective, but that's what Nintendo wants the mainline Mario series to be, and that's what it is. If you're looking for something different, you're probably looking to the wrong franchise.
Italics made me laugh :D
Okay, let me get more specific. Have you ever played Shadow of the Colossus?
There's a game with very little story, yet for some reason it had a GREAT untold story. There is so much you are thinking must have happened in that realm, yet little of the story is told. And like Mario, it doesn't need a story because you're going from Colossus to Colossus. However, like Sal gave in his example, in Journey (which I have yet to play), there is a great untold story, told with the dynamics of the characters, with the environmental objects and worlds you cross, told by the swaying music. It doesn't even need a story that the game conveys an emotion. (@Xxain, read that it'll answer your story whore question).
The last paragraph is one that troubles me the most and I'll tell you why. Mario is a character that represents the company as a whole. It's the icon of the company, and close enough to being the icon of the industry. Should a character with such a great reflection convey vaccuity? Or should he convey emotion? I believe emotion.
When Super Mario offers themes that are limited to children, it alienates the folks who are older who would also like to enjoy it. As such, many in this thread say it is the example of a game that is not age restrictive, but it is the exact opposite, it restricts to kids. On the flipside, nothing in Disney movies makes me, as an adult, and as a child in the past, want to shut it off. Rather, I want to stay and watch it.
That's the all-encompassing quality a Mario game should have, as the icon of Nintendo. Anything else would be selling it short, to make a pun. ;)