Still adding and refining the list of effects. Too powerful and ... naah, casters will still rule, just less absolutely. Too weak hasn't come up yet since any emulated spell makes the skills far more useful than they are presently. Makes skill monkeys and even melee types much more useful, and more importantly, fun. Thats a game system change though and not relevant to the rebuilt Fighter.
Well too strong is the same issue as magic being too strong. If you can no longer effectively challenge players in a certain domain, theres a problem.
As for the Fighter in particular, I'd look at the staples in the areas they are supposed to cover.
Movement - Fighters need to move, especially melee types. Whether realistic or fictional, they are supposed to be athletic and highly mobile compared to others. Platemail is slow, but only relative to leather clad archers and mounted warriors in general. The only type of Fighter that in a realistic environment would be genuinely slow in action would be pikemen footsoldiers and thats because they are supposed to stay there.
In game, they're at a profound disadvantage. Meleers MUST move to get into position, and being slow slays them at their own game. They cannot move and deliver their expected performance(ToB helps here with standard action stuff, as does ubercharging). Add to the fact that many monsters can run circles around even a 30ft move(much less the 20ft that heavier armors would bestow) and that every outsider that matters can teleport.
At 1-5, their armor makes them slower than the wizard, before any magic comes into play, unless they had a mount. In addition, TWFers learn that they don't get to move and use their second attack unless they're mounted. They
might be passable at feats of athletics like climb, jump or swim, if they had the skill points to spare, but Spider Climb, Jump and water breathing magic are going to blow them clean out of the water.
At level 6-10, it gets worse, full attacks have just come online and you can't move and use them without shenanigans(I know Pounce is practically a staple, but by the core book its not exactly available). Lose a third of your offense whenever you move, even as flight and short teleports just joined the table. Mounts are also expiring, they die fast for any you can buy, whereas the Ranger at least gets a useful ride.
By the teen levels, their maneuverability is completely obsolete, and legit mounts have completely fallen off the table(of course, theres Warbeasts). Planar travel they can't do. Allocating magical wealth to dealing with these is difficult, what with the expensive basic melee equipment and the many holes they're filling.
So to fix maneuverability, they need
1 - To be able to do their thing while moving. Archery Fighters have manyshot, mounted fighters need to be able to either get better mounts systematically or else buff their mounts to useful levels just by sitting on top(I favor this one, e.g. by giving their mount some Familiar benefits(specifically, sharing health, BAB and Fighter feats while the Fighter is on top), TWF fighters in particular and melee fighters in general need to get rid of that full attack business(maybe a full attack just adds one more attack, or maybe it does away with iterative penalties, not sure how sane the latter is) for something they can do as a standard action(i.e. the regular full attack).
2 - Super Movement, for lack of a better word. Swim speed(with enhanced lung capacity for free), Climb speed, general speed boosts as they level. Later on air walk and burrowing, moving onto Plane Shift eventually. Move action short range teleportation may be in order as well.
Direct Contest Fail - Size is the big offender here. Anything besides hit target with weapon requires a check, which is often modified and limited by size. The bonuses from size easily overwhelm anyone who hadn't whored that one move out to the exception of anything else. The bonuses from monstrous strength make it worse(especially for checks unmodified by BAB). To add insult to injury, casters can access, or give access to these bonuses via polymorph.
Fixing this can take several ways.
If you're doing a basic revamp of combat mechanics(after all, hell, the grapple rules are a clusterfuck, might as well), making the checks modifed by BAB+Stat, reducing the scale of the size modifiers(if Large gave +1, Huge gave +2, Gargantuan +4 etc), makes the numbers more reachable. Making certain maneuvers easier to smaller creatures may help. Also, the absolutes(e.g. the maximum size you can grapple) need to be purged. And of course things like Freedom of Movement giving total immunity to grappling as well.
Alternatively, improve the Fighter by granting virtual size categories for the purpose of combat maneuvers.
Defense means nothing - AC and hp just won't cut it at higher levels. They'd hit all the time and for more damage than your hp within one or two full attacks. More a problem with melee in general, but if you can get hold of effective DR and energy resistance without resorting to magic, that'd be nice.
Variety of offense - Combat maneuvers are horribly limited. You can disarm, trip, move an opponent a pathetic distance, and thats about all the practical ones. Throw in some decent status effects to tag onto attacks, ranged or otherwise. Battlefield control can be created with stunts that alter common battlefield aspects, like hitting the ground/wall to both create difficult terrain and an obstacle.