I'm cool with the current system, they just need more unique upgrades for each path.
One of the most similar leveling systems I've seen to this games is the HoMM5 system - each faction had a web of upgrades for certain classes of heroes: http://www.celestialheavens.com/viewpage.php?id=520
The outer ring of skills would be somwhat analagous to the 'Path of' traits here, with each outer skill unlocking subskills, and combinations of those skills leading to 'ultimate' skills in the center of the ring.
A similar system could be used here, where a broader range of traits are accessible to each path, and picking certain combinations unlocks the possibility of more advanced traits showing up.
Another option would be the combination of multiple paths traits unlocking new paths or new traits.
Really there's a lot they can do with the current system, it just needs more development. The current path trees are very shallow and mostly bland, but it's so easy to think up new traits/combinations/branches, I'd be amazed if they are content to let it lie as it stands now.