Problem is a rather harsh word though. It was a compromise that could be a improved upon a bit while still holding up the primary tenets of the compromise.
IMO It almost seems like you are waging this battle in the name of another war. I brought up the comparison with the rogue (a martial class that's generally praised for being solidly designed for all pillars) to show that there's only a few things the rogue gets in heroic tier that help it out of combat. Even so, no one complains about the rogues out of combat capabilities relative to casters or even it's fighting ability relative to fighters. To me that indicates that the 'issue' is your desire for the fighter to be even better out of combat than the current rogue and not actually some overarching problem with the game itself. Heck with feats the heroic tier fighter likely trounces the rogue at combat.
I think the fighter could use a minor buff to out of combat capabilities. There's a few forms that could take. But all he's lacking out of combat when compared with the rogue is really 4 skill expertises. (Yes that does change some at higher level, but improving the first 10 levels would go a heck of a long way.