letters to nintendo 2 (spin off characters are not "new" characters)

[thekitchensink]

Yeah, the only characters on that list that I like are Diddy, Wario, and Daisy (besides the babies)

But still, you're exaggerating quite a bit. Over the last several years they've introduced plenty of new characters. I'll only list characters from N64 and beyond, since you ended at SNES.
Mario games:

Bowser Junior (different from the Koopa kids)
Kammy Koopa
Petey Pirahna
Princess Rosalina
The lumas
Dark Mario (I know he's baby bowser in disguise, but he's still his own 'character', like Shiek is)
The Piantas
The Penguins (from 64 and Galaxy)
Cackletta and Fawful (Mario and Luigi)
Count Bleck (Super Paper Mario)
Dr. E. Gadd
The ghosts from Luigi's Mansion
All the party members from the SPM games (though they may not count)
FLUDD (I'd say it counts as a character)
Stuffwell the briefcase
ROB (Yes, he was a peripheral 25 years ago, but he only recently became a character in Mario Kart DS and Brawl)

Donkey Kong:
All the evil enemy apes from Jungle Beat (which I haven't played)
Admittedly can't say much here, since DK hasn't had many of his own games lately.

Metroid:
Dark Samus
10 new hunters from Prime 3 and Hunters


Zelda (I'll try to include only characters that were major, since each Zelda has a unique story):
Saria
Navi
Midna
The fairies from Majoras mask and PH
Shiek
Ganondorf (on SNES he was only Ganon, the pig-man)
Wolf Link (debatable)
Young Link, Young Zelda, Young Saria (since baby mario/luigi/etc count)
Toon Link
Tetra
The talking boat
Captain Linebeck
Zant
The main enemy from Four Swords (whose name I can't recall)
(I haven't beaten PH yet, or played Minish Cap)

Star Fox:
Wolf
Pigma
Oikonny
Leon
Dash
The Krazoans
Tricky
Krystal



Still think Nintendo never adds new legitimate characters anymore?