I mained Mario for quite a while and I believe he is at about the right place on the tier list. He definatley deserves middle tier, though maybe a little lower in it. I would put him as the lowest ranked in mid tier, because Ganon being there just seems wrong. Mario basically has trouble finishing the job. He has a ton of combo starter, and even more combo filler. He is a combo machine, plus he has a projectile, not a good one but at least its there. The obvious problem though is that he can't get KO's. He just builds up all that damage and can't do anything with it. He is almost entirely realiant on edge-guarding for kills, thankfully he is good at that. One of his other problems though is his terrible range. He has pathetic range on his normal attacks, and his grab range is just depressing, especially considering how much he relies on his great combo starting grabs.
So pretty much Mario gets locked into a war of attrition. For him to KO he needs to do more damage than the opponent does to him. Other characters can KO opponents at lower percents so they don't need to stick in for the long haul like Mario does. His range makes this an even bigger problem, since your opponent will often have more opportunities to hit you than you do to hit them.
But still he isn't all bad. The cape makes him above average by itself, and once you implement things like SHABAWD into your game, and learn to edgeguard well, he can become quite good. Still though his weaknesses are pretty big, and I couldn't see him moving any higher in the tiers.