I knew what you meant, but I thought it prudent to clarify that new materia for materia's sake is possible to create. It might be interesting/important to note that magic, summon, and several command materia needs to stay as is since they're used to create Master materias. You could still create more magic materia, but if you want the Master Magic to reflect it, that's yet another issue to resolve.
Still, you could create different materia. I always thought a low-level, mid-level, high-level materia was in order.
Low-level:
Fire (initial),
Ice (100 AP),
Bolt (200 AP),
Quake (350 AP),
MASTER at 1500 AP
Mid-Level:
Fire2 (initial),
Ice2 (1000 AP),
Bolt2 (1500 AP),
Quake2 (2400 AP),
MASTER at 5000 AP
High-level:
Fire3 (2500 AP),
Ice3 (6000 AP),
Bolt3 (9000 AP),
Quake3 (15000 AP),
MASTER at 15000 AP
Then Contain has the "Ultra" level spells. The AP would likely have to be increased and the spell power would have to be adjusted to account for the later acquisition of Ice and Bolt. I think this would be a more natural progression (So you can't get, say, Ice3 before you are able to buy an Fire materia) so long as you don't allow access to the high-level too early in the game.
This is the issue I'm talking about. Mastering this won't count toward a Master Magic unless you replace Ice, Fire, and Bolt materias with these. Then to keep the game balanced you'd have to get rid of all references to Fire, Ice, and Bolt materias until later in the game. This would even free the Quake materia to contain up to four new spells!
This would also likely mean no early Beta learning since You'd have to take the elemental attribute off of these materia. That is, unless you want to give elemental attributes to command materia... Ya know, this is starting to be a really good idea.