There was a thread with the exact same subject a while back. . .if anyone cares to search for it and drudge up what was said then, the same things should still apply.
Basically, Mario has problems against characters that 1) have incredible range/priority, 2) are extremely floaty, and 3) have excellent recovery.
Range Priority Issues
The range/priority issue is a problem for Mario simply because he tends to be a short-ranged character. None of his aerials have the kind of distanced range that, say, Falcon's n-air or Doc's b-air has. Go into AR and you'll see that the hitbox size for his attacks--including his grab--is abysmally small. What this means is that anytime Mario goes up against a character that has better priority/range, Mario is automatically disadvantaged, because he'll have a hard time getting in close and starting the combos he needs to win.
Floaties
Floaty characters also present a serious problem. Remember that Mario is, in essence, a character that trades in KO power for sheer combo potential. Without combos, Mario's crap. I was in a mini-tourney today, where I had to fight a Ganon. . .I focused too much on being evasive, and I got 3-stocked. When I played the same guy 30 minutes later, I focused on grabs and combos only--and I won.
The point here is that Mario requires combos in order to win. When you're up against floaties, Mario's combo potential significantly drops, because his shffl'd u-air chains, u-tilt/u-smash/u-throw convential comboing doesn't apply any more--they just float right out of it, and n-air. Against floaties, Mario's game is reduced to relying on very simple hits instead of the extensive combo game that most people associate with him, and he suffers for it.
Characters with Excellent Recovery
Mario can't KO. He has low KO potential; therefore, anyone that has relatively decent recovery--like Samus, Jiggs, Peach--are going to pose something of a problem for Mario, simply because he can't kill them as quickly as he would like. They keep coming back, they soak up more damage, while Mario has to try and KO in a stupid game of attrition, hoping that he'll KO before he accumulates any more damage. It's not fun.
Keeping all of this in mind, just figure out which characters belong in 2 or more of these categories, because these are all areas in which Mario suffers. . .he has crappy range, has better combos on fastfallers as opposed to floaties, and can't KO. Therefore, any character that has great range, is floaty, and has excellent recovery poses a threat to Mario.
So, if I had to pick out who Mario has trouble with the most, it'd be:
1) Marth
Marth has great range, and is pretty floaty. . .and though Mario can combo him relatively well, the problem is that his f-air will break through all of Mario's combos. About 95% of the fight is trying to get inside sword range, which is already a huge problem, since his grab and hitbox range all exceeds yours. . .but even if you do get inside, his floatiness and f-air make combo'ing nigh impossible. Really hard matchup IMO.
2) Peach
Peach has great priority, excellent recovery, and she's also floaty. . .I'm fairly convinced that Peach amounts to something of a Mario counter, in some way or another. Everything that Mario has, Peach has--but better. Better aerials, better combos, better projectile, better recovery. . .Mario just suffers in this matchup because he won't be able to get in clean hits, he can't combo, and she just won't die. Luckly, u-tilt and shffl'd u-airs *sort of* do well in ranging against float-cancelled aerials, but again, it's Peach. It's not an easy matchup.
3) Samus
Samus fits into all 3 categories, but luckily enough, Mario does have the advantage of speed in this matchup. It's very much possible to put enough pressure on Samus so that she'll have little time for missile-cancel setups, and force her to rely on her melee game entirely. Shffl'd u-airs, selective caping of missiles and sheer speed make this matchup a lot less scary than Peach or Samus. . .but still, her sex kick and bombs make comboing incredibly difficult, and KO'ing her--especially on stages like DL64--is a nightmare.
Jiggs deserves an honorable mention in there somewhere too. It's lucky for all of us that it dies relatively early, so that kind of evens out the playing field.
And supermariopro, Fox isn't really a difficult matchup for Mario. It's about even, perhaps with a slight advantage on Fox's side. Yeah, Fox has all that cheap ****, but Mario has equally cheap stuff as well. U-throw chaingrabbing into combos is what Mario does best, and Fox really suffers from that. Of course, it boils down to whether or not Mario can actually grab the Fox in the first place. . .but provided that he does so, the matchup isn't nearly as awful as you're suggesting.