This is probably not a new suggestion but here goes.
There are tons of prestige classes from the PnP game that are dependent on being skilled in multiple classes. This functionality could improve the versatility and power of the multi-class system fairly well. Granted it would be tricky to balance it so that it can both stand up to the trials of the higher game and also doesn't overshadow a well-made single-class build, but it would still be nice to have.
For example, Mystic Theurge, while something of an over-powered gumby on PnP is still a fun concept and would be nice to have. And then there's my own preferred combination: Paladin/Rogue, which has a couple of obscure prestige classes for it, mostly related to specific faiths, but could be played similarly to the Avenger concept (4e divine striker) or as an Inquisitor.
My suggestion would be for the upgrades to come available at levels 8, 14 and 20 for example:
Requirements: Paladin 4, Rogue 4, Paladin Extra Smite I, Rogue Improved Trap Sense I
Any one of: Rogue Improved Spot, Rogue Improved Bluff, Rogue Improved Search, Rogue Improved Disable Device
Any one of: Paladin Improved Intimidation, Paladin Improved Concentration, Paladin Bulwark of Good, Paladin Improved Diplomacy
One of every 4 Paladin levels count as a Rogue level for general enhancements, sneak attack and uncanny dodge.
One of every 4 Rogue levels count as a Paladin level for general enhancements, smite evil damage and turn undead power.
All Rogue and Paladin skills always considered class skills.
This enhancement ceases working if Paladin and Rogue are more than 3 levels apart.
Requirements: Paladin 7, Rogue 7
Half of all Paladin levels count as Rogue levels for general enhancements, sneak attack and uncanny dodge.
Half of all Rogue levels count as Paladin levels for general enhancements, smite evil damage and turn undead power.
Add sneak attack damage to smite attacks if a sneak attack would be possible normally.
This enhancement ceases working if Paladin and Rogue are more than 2 levels apart
Requirements: Paladin 10, Rogue 10
All Paladin and Rogue levels stack for general enhancements, sneak attack, uncanny dodge, smite evil damage and turn undead power.
Sneak Attacks are considered to have the "Good" alignment for bypassing Damage Reduction.
The player would sacrifice the third Stat boost for each class, the class-specific PrE's and their capstone, they wouldn't have as many skill points as a full rogue or as many hit points as a full paladin...but would still be effective.