Materia is a slot killer, especially if they will be reducing slots in the future. For us Yuffie's out there materia is an awesome way to make gil and kill time (woot for Spiritbind parties). Here are my suggestions:

-Retainers have a "Materia Chest": Have a tab on retainers only that can hold up to 100 materia. (You can even attach a side quest to obtaining the materia chest)
-Simplify tiers and have them stack: Tier 1,2,3,4 = +5,+10,+15,+20, respectively. Then make tiers stackable.
-Materia upgrade: Have an NPC out there in the world I can exchange 10 Tier 1 materia to get 1 Tier 2, and so on.

I like everyone else's ideas, too. Just so long as something is done about the materia.