First up: Flavour
Personally, I couldn't care less whether a purely mechanical class such as this has flavour or not. I'm one of those people that thinks that any part of any publication which says "here's how your character acts" is a waste of space. PrC's don't need to be linked to flavour. Flavour should stand independant, with references FROM the flavour TO the mechanics, not vice versa. Most red wizards are group-oriented, power-focussed specialists. Most group-oriented, power-focussed specialists are NOT red wizards. Flavour text for the Red Wizard PrC is wasted on anyone not gaming in the realms, or using a similar organisation in their own campaign, one which could be run just as well without the PrC.
That's part of 'options, not restrictions'.
Next: Balance
People seem to be saying "one mystic theurge is better than a wizard, because of all the things he does for the group".
That's not the right comparison. The comparison when you're getting into team-mechanics isn't between the power balance of each individual making up the group. It should be between groups. This brings the effects of buffs and extra healing into some real perspective - sure the character can do it, and depending on the person playing it, he may enjoy doing it, but does it actually make the party much stronger? Does it throw the CR system out?
Which would you rather be in? The standard fighter, rogue, wizard, cleric group, or a fighter, rogue, theurge, theurge group?
Personally - I couldn't make a decision. In one group, I'm going to get high power buffs, and have enemy monsters crippled by high-level magics, but the group will have to stop and recoup often. In the other group, I'm never going to be left wanting for hitpoints or low-level buffs, and the group will be able to continue and endure for a long time. The two groups would be different, but I don't think you can honestly say that either would be inferior to any significant degree.
Another one I'm seeing here is that you have to compare levels in theurge to levels in something other than theurge, and that you cannot take into account the 'cost' to enter the class.
That's just plain wrong. You cannot compare just a single part of a character to a single part of another character. You'd end up with arguments like "the sorceror is overpowered because at 4th level, he can cast more spell levels per day than a wizard and he gives up nothing". You have to compare the entire character.
I believe that introducing a prestige class to overcome a flaw in the rules is an acceptable solution to the problem in a product which is not intended to be a completely new version of the game. An entirely new magic system would certainly NOT be compatible with the existing system, nor would it be easy to convert to. Introducing prestige classes is a solution which both works, and is backwards compatible with very little effort, impacting only upon those characters which chose to multiclass cleric/wizard.