Sorry if that sounded a bit offensive, but I've read the Luigi argument so many times that I'm a bit tired about it.
Let's see.
And what do you think is a "legend?" Look around this board. There have been many, many character suggestions here, and most characters are popular, but are not "legends." There's a huge difference. And here are characters suggested in the Japanese poll:
King Dedede(5)
Diddy Kong(4)
Geno(4)
Ike(4)
Ridley(4)
Captain Olimar & Pikmin(3)
Krystal(3)
Takamaru(3)
Windwaker Link(3)
Animal Crossing MC(2)
Claus(2)
Demiru(2)
Isaac(2)
Jeff(2)
Kawasima(2)
King K.Rool(2)
Lip(2)
Lucas(2)
Mega Man(2)
Oguma(2)
Ouendan(2)
Sukapon(2)
Would you consider any of them to be "legends?" Why do you think that the poll was created? Were they just bored? The point is that Nintendo doesn't just say, "Hey! That guy has been in a bunch of games! Let's put him in!" They actually listen to our suggestions. Toad is a very popular character, so he has a chance to be in the game. Waluigi is popular, and has a chance to be in the game.
Ok, most of these characters are legends or important characters for Nintendo and its respective franchises somehow. Sukapon is a sort of obscure and cult legend, but legend nonetheless. Kawashima is the mascot of the new line of successful Training products. Ouendan is one of the best bemani games and it's regarded as a complete success in Japan and overseas. Dedede is legendary, as Geno, Ike, Ridley, Takamaru, Olimar, Lip... all of them.
Waluigi can't be proud of anything: "I'm the skinny guy that appears in each party game with Wario". Toad, Toadette, Petey Piranha, King Boo the babies, Birdo, Bowser Jr and even the Koopa Troopas can say that too. That's not a feat.
Someone said that Brawl could be Waluigi's trampoline to the fame: He will get a solid background and the acceptance from participating in such an important game, but Smash Bros. should be the place for the characters to show what they've done through their career, not to start. Yes, Roy appeared in Melee before his own game, but his role in the Fire Emblem was decided beforehand and the Fire emblem franchise was in its lowest: An advertisement for the upcoming game was needed and some say that Roy appareance in Melee was what boosted the sales and popularity of Fuuin no Tsurugi and the resurrection of the franchise as a final goal.
Even Tingle, who has its own game, won't get in Brawl. Tingle have gone through a lot and finally he got recognition, yet he has a long path to walk before making it to the next Smash Bros. (if there's even one). Waluigi hasn't done any of that. It's because Nintendo, but this is what he has right now.
Even WARIO didn't appeared in Melee, having many games, appareances and popularity (I was really upset as a Wario fan), and they waited to him . Waluigi won't get this time, he lacks many of the traits of other Smashers.