It's my opinion that Ness's reason for generally sucking isn't attributed to his late addition to the game, but rather his role in N64 Smash Brothers.
As far as Meta game goes, Ness was GOD mode in N64, at the Intermediate level. And as we all know, N64 Smash never realized the same level of success as Melee, therefore the majority of Ness players were intermediate. HAL saw this, and nerfed him accordingly. Unfortunately, they nerfed him a little too hard.
As you can see, his most powerful moves (remember, speaking at the intermediate level, not at the advanced level), have become his some of his worst.
PKT2 could propel Ness... probably in the area of 20 body lengths in N64. Now I'd guess the number to be closer to 6-8.
Additionally, look at his Down-Air. In N64, the move was instantaneous and long lasting, to the point where you could spam it for a 0-death combo. Now, in Melee, it has horrid lag and has a quick hit box.
Anyways, it seems that Ness was just nerfed a little too hard.
This is my opinion as player whose main was Ness in N64 and still is in Melee.
Regardless, I still believe that Melee Ness's true potential has yet to be unlocked, much like Falco or Ice Climbers were initially.
It's beginning to happen though. There are combos which I've pulled out on friends that make their jaws drop (0-death on fast fallers using nothing but U-tilt, U-air and U-throw). The secret lies in DJC SHFFLs. At the very fastest level, you can throw them out faster than wavedashes.
Time will heal Ness, as the few players who play him grow in skill level (hopefully).
But it is tough being the underdog...