Actually, the latest tier list as of pre-Brawl was the 2006 one, and Mewtwo was dead last on that one, just to elaborate on it. Many of the other bad characters were either big Nintendo stars (Kirby, Yoshi, Bowser) or also disliked (Pichu, Young Link, G&W.)
It's a combination of his awkward playstyle, being a bad character overall, and his fading popularity inside the Pokémon franchise itself. Mewtwo's floaty fighting style never fit very well in Melee, and it was as if he couldn't decide whether he wanted to be a heavy hitter or what he wanted to be. On the other side of the bowl, Mewtwo was beginning to fade away in the Pokémon franchise. In 4th Gen legendaries became much more common, and Mewtwo hadn't seen the spotlight in a long time, and on top of it all a new Pokémon had claimed his crown as the most powerful Pokémon ever. Suddenly he wasn't very notable anymore, he was just like every other legendary Pokémon, perhaps even less important than many of them due to not being a game mascot. Then there was also Lucario, who was a very popular Pokémon and character request at the time, and people were already drawing comparisons between Lucario's aura powers and Mewtwo's psychic powers back then, which is where the fight began to begin with. There were a lot of factors that tied into Mewtwo getting cut from Brawl, and to be fair not that many people were furious about it back then, they were too busy complaining that Geno and Ridley weren't in. It's only shortly before SSB4's announcement that requests to bring him back exploded suddenly again, coincidentally when Mewtwo was brought back into the spotlight in Pokémon.