The magic system/UI/tree is so bad, I had a very hard time even coming up with a suggestion on how to improve it. Eventually though, I realized the system could be very fun and very strategic if done in a certain way common to other titles.
1) I'll leave the UI out of this and get to a conceptual idea. Magic is lost and being rediscovered therefore, spells should need prerequisites to progress. Similar to Diablo but on a much larger scale. This would have lots of strategy/tactical feel and allow depth within each magic tree or breadth within many different trees. You can't even use that fireball II scroll you just found until you research fireball I.
2) This concept can spill over to custom sovereigns, giving magic tree specialty/depth and perhaps an early advantage at the cost of something else. It's not just that the sovereign can cast from Life magic, it's that he can cast life magic at a discounted mana rate, or that he starts with multiple spells within that tree etc. Lots of wiggle room here.
3) A definite feel for each tree would help immensely, similar to Magic the Gathering of 5 years ago or so. Each tree had a feel to it with very little overlapping. If you wish to summon endless hordes, it's X magic tree, if you want to just rain fire from above, Y magic tree. That said, X tree can't reign hell from above and Y can't summon good creatures. Even the magic trees themselves could become a very strategic part of the game, perhaps one tree has a large focus on world manipulation and another is all combat based and yet another is all industrial etc. Hybrid wizards or theory would quickly result with favorite tree combinations and depth within. No 'common' spells if at all possible as it ruins the feel for the tree separation.
4) Trading of knowledge via scrolls would also be pretty interesting as a diplomatic piece. If you don't have any use for a dark magic spell, trade it to someone that does for a hefty price. If not the knowledge itself, scroll or books found for sure. Oh sure, I'll trade you Mass Drivers for that entire star system. (MoO 2 reference *cough*)
Recap:
1) Prerequisites for each spell can force strategic decisions and planning like Diablo.
2) Sovereign specialties in specific magic trees for depth and potential strategy.
3) Stylize a magic tree for spell selection similar to MTG. (with no common spells to all trees)
4) Diplomacy your useless (for you) spell scrolls or books.
-AceQ-