To try and keep it uncharacteristically short, I'll jump right to my idea.
Keep the prestige-tree idea, even 3 per class, but take a handful of enhancements that are fairly CORE to the class you're in and present them similarly to the current core enhancements, as a row on the bottom of the UI leveling horizontally instead of vertically, but place them outside the trees. These could be level-gated or AP-spent-in-class gated, but there should be at least two rows of options, so that players who don't want one will probably want (and take) the other. Reduce the AP Spent In Tree requirements on the PrEs (or remove them entirely) and give us back the Total AP Spent. Change the current Core PrE abilities to auto-grants, as they appear to be to anyone that has spent time with the epic destiny system.
A cheap mock-up (because my Photoshop-fu is weak):
[ tree 1 ][ tree 2 ][ tree 3 ] - one tree per prestige
[ tier 5 ] [ ] [ ] }
[ tier 4 ] [ ] [ ] } enhancements in trees have rows and columns, with
[ tier 3 ] [ ] [ ] } advancement represented vertically, as we have currently.
[ tier 2 ] [ ] [ ] } these would only be enhancements tied directly to the PrE.
[ tier 1 ] [ ] [ ] }
[ Auto-grants ][ ] [ ] -- these would be given automatically as AP is spent in tree
[ Generic core class enhancements ] } two rows of core class abilities here, providing options so
[ Generic core class enhancements ] } players don't feel locked into choices they don't want.
Tier 5 could continue to be gated by 8 or 12 class levels, with capstones requiring 20 levels in your class, and maybe restricting you to one set of tier 5 abilities on a character, unless you have 20 class levels, at which point you may pick up a second set of tier 5 abilities (a reward for staying pure that actually competes with multi-classing without being an obvious choice IF there are enough worthwhile enhancements to take up 50-80 AP in one class). Tiers 1-4 can be gated by class levels 1-3 or 4 as they are now, along with total AP spent (as on live). Trash the really junky enhancements that no one wants, like Wand and Scroll Heightening, cost enhancements appropriately (1 AP per rank for moderate improvements, 2 AP per rank for big improvements, especially for single-rank enhancements that provide new, useful abilities), and add a greater number of really valuable enhancements so that the real gating is done through choice; having to make choices based on your 80 AP hard cap, rather than sinking AP into junk filler for AP spent in tree or arrowed prerequisites.
The generic core enhancements should be aimed at two prevailing archetypes, or roles, in a class, in order to provide real choices to a wide variety of players. For instance, a rogue would have a row with, say, Sneak Attack Training, Haste Boost, Damage Boost, Wand and Scroll Mastery, and a row with Skill Boost, Faster Sneaking, and improvements to core skills. You could pick from either row, or both--the idea is just that you don't have to spend AP on one of those things, when you don't care for the other, just to advance in the class' enhancements.
Another benefit to the idea, is that the three-tree limitation isn't quite so restrictive to heavy multi-classers, since even if you pick two PrE trees from one class, and one from the other, you would still be able to acquire some core enhancements for all three of your classes.