I see no problem with letting players switch out skills—as long as they give an acceptable reason why it fits their concept. The PCs are supposed to be heroes and adventurers, they should be adequately skilled.
As for 'balance', some people don't seem to realize that balance isn't all in the rules, it's in the make-up of the party and the judgment of the DM. If everyone has Hide, Listen, Move Silently, Spot, Search, and Tumble, so be it... the party is really good at stealth. However, they will suffer elsewhere. Especially since it's the DM's job to challenge the party. If they are too sneak-heavy, hit them with diplomacy-bluff-knowledge based adventures now and again to keep them spending cross-class points. Or even start having their opponents use very perceptive pets...
An option I'm using is to have "careers" that contain various skill-sets. For example:
FIGHTER
• BODYGUARD: Concentration, Intimidate, Listen, Profession (Bodyguard), Search, Sense Motive, Spot
• MERCENARY: Appraise, Climb, Craft, Intimidate, Profession (Mercenary), Ride, Spot
• OUTLAW: Appraise, Climb, Intimidate, Hide, Profession (Outlaw), Spot, Survival
• SEAMAN: Balance, Climb, Knowledge (Geography), Profession (Seaman), Spot, Swim, Use Rope
• SOLDIER: Climb, Craft, Handle Animal, Intimidate, Profession (Soldier), Ride, Spot
• SQUIRE: Craft, Diplomacy, Handle Animal, Intimidate, Knowledge (Nobility), Profession (Squire), Ride
• WATCHMAN: Gather Information, Intimidate, Profession (Watchman), Search, Sense Motive, Spot, Use Rope
Everyone gets Profession, which covers knowing the 'details' about their career.
Everyone also gets one free-choice skill to represent a specialty field in the career (i.e. Merc beast-master with Handle Animal). This skill needs DM approval.
Note that I've given the FTR 7 skills. As I think 2SPs are enough of a limitation, access to a wider variety does no harm.
Also note I removed Jump as a skill (it's an ability).