I have a suggestion, somewhat lifted from the Warblade. Allow the Fighter, as a master of weapons and combat, to retrain any Feats that specify a weapon (Weapon Focus/Specialization) by training with another weapon for 8 hours.
This gives the Fighter versatility, makes them feel more useful (since a new weapon or a change of concept for the character is easily done) and flows pretty well with the game anyhow. It's a small ability, easy to inject that adds flavor and a little kick to the Fighter class.