High-level heroes tend to have a huge list of unrelated traits, too long to keep track of.  And most of my heroes end almost the same as I pick the same traits for all of them.

My fix would be to have a lot more traits with stages 1 to 3 (or higher).  Convert a lot of the existing just-once traits to have stages.  Then bias the level-up system towards offering the next stage the traits the hero already has instead of offering completely different traits.  Maybe do it this way:  assume that a hero must be at a certain level to get the next stage of any trait -- then once he hits that level it always offers the next stage of the traits he has until you finally pick them.

It might also help to limit the number of "path of the..." traits a hero can have, as suggested elsewhere, but I have one big concern -- I want more melee specialist heroes (largely so I can autoresolve without losing all my mana in easy battles) and too many of the heroes I find now have "path of the mage" and two or more spellbooks.  Locking all of them into being mages forever would be horrid.  If they go this route I think they would have to redesign a lot of heroes first to add more warrior/assassin/governor types.  A limit of 2 or 3 paths might be ok, with the 2nd available soon but the 3rd not available until he reaches a high level, but a limit of just 1 -- ugh.