His Size
His size is problematic. Quite a few characters can force him to jump release out of their grabs, which leaves MK almost always vulnerable to attacks or even regrabs. Most ppl ignore me when I bring this one up or just come with some strawman arguments: "MK is too hard to grab and these characters suck anyways lololol". This is rubbish. In Melee spacing was due to Wavedashing much "stricter" than in Brawl but you could still grab any top tier character if you get the chance. Marth had more range than MK has now (comparably) yet MK is supposed to be magically un-grabbable? This is obviously complete garbage. Jump releases must be considered a disadvantage against MK. Here's are some facts...
Characters, that can force MK to jump release: Donkey Kong, Zero Suit Samus, Marth, Zelda, Sheik, Ike, Ganondorf, Captain Falcon, Bowser and Peach (if anyone's missing, let me know).
Out of all these characters DK seems to be the only one who get's no free attack. All the other characters get one guaranteed attack. Ike, Peach, Zelda and Marth apparently only get a free dash attack. They either deal less dmg than a throw or have no KO potential. In most cases both is true.
However, Ganondorf, Falcon, Sheik, Bowser and Zamus will have better options. Ganon gets a free downB and Falcon even has a CG apparently but since both of them suck I'll even leave them out. That leaves us with Bowser, Zero Suit Samus and Sheik.
- Bowser: has a CG only due to MKs size. It also gives Bowser plenty of free attacks and often KO moves. With it he can KO MK with 0% at the second stage of Castle Siege (so much for the no counterpick argument).
- Sheik gets a free boost smash. Kills at 83% (center of FD + training mode)
- Zamus gets a free sideB. Apparently she doesn't even have to move. Kills at 105% (center of FD + training mode)
...
No matter what you think about it, it's a weakness that's in fact almost exclusive to MK. Other characters have the same weakness but they are not of interest now.
Good DI is bad for MK
Many ppl seem to be unable to DI MKs attacks correctly. Otherwise they wouldn't complain. If you can DI out of his moves correctly, half the work's done (honestly I'm more afraid of Sonics techchases than of MKs tornado). If you manage to DI correctly you'll see that many moves of MK have some weak spots, that you can exploit. The most obvious example is the tornado: The top center has almost no priority at all and it just happens to be the spot that you can reach the easierst via good DI. If you DI correctly (up+away) and fast enough, you basically just get a free Dair and in many cases, they deal much more dmg than the first few hits of the tornado do. Most dair deal between ~15% (Peach, Yoshi, Pika and many others) and ~20% (Ganon, Yoshi, Snake). Some of these moves have KO potential such as Links dair. That means: even if you fail to shield the tornado (completely shielding it leaves him open too btw) you can still avoid most hits. You'll take ~8% dmg but are able to deal twice as much. Tornado isn't a safe move. You don't even need to shield it to have a good weapon against it. That's the "fate" of weak multi-hit attacks in Brawl. You can DI at almost any time out of most of his moves and bring yourself in a better position for a free attack or a risky lose / lose situation for MK. The Shuttle Loop is such a move. It has little start-up lag, invincibilty frames and seemingly transcending priority but it's actually full of weak spots, that put him in bad positions.
Just in case: Snake, King Dedede, GnW and Donkey Kong don't have many moves like that, that bring the user in bad positions. Few characters have such moves at all. MK is one of the only (higher tiered) characters, who has such issues.
His weight
One of the only things that's accepted: MKs leight weight make him easy to KO, even with his godly recovery. Most ppl will tell you that he's strengths will outweigh this flaw. Of course they do. MK is top tier for a reason. But Snakes strengths outweigh his weaknesses too. That's the nature of top tier characters. What stays is one recognition: MK does have a weaknes.