Kristyn,
If I were you, I would always maintain the interaction hierarchy, i.e., I would include all lower order interactions that were components of a higher order interaction. That might mean that the 3-way interaction cannot be included, and although it represents your research hypothesis, there is scant point in including it if the model is dysfunctional.
Re (3): The facts (a) that the ANOVA-like model works when the 3-way interaction is dropped and (b) that regressing on Age_Group works both support @PaigeMiller's suspicion that the data structure is inadequate for a 3-way ANOVA-like fixed effects structure. Regression on Age_Group could be a viable alternative, provided that regression makes sense (i.e., that the distance between the levels of Age_Group are sensible in the sense of "one unit change in Age_Group causes some number of units change in logit(Y)" and that the relationship with the logit is linear). You would need to be careful about how you specify RANDOM statements for the model incorporating regression.
Paige's point that "you may have some of the multinomial levels at zero for some of your design" makes sense to me. Try various cross-tabulations of TaskPerformance, Age_Group, Condition, and Task. You may find marginal zeros (absence of observations for certain combinations of TaskPerformance and one or more predictor variables), which would I think generate the problems you are having. The topic of "sampling zeros" is addressed in the log-linear model literature; the logit model is derived from the log-linear model, so that literture is pertinent.
Re (5) I have never seen results change as a consequence of order, and I have fitted a lot of models to a lot of data. But, that said, I have fitted very few multinomial mixed models. So it might be a "feature" of that sort of model. That's an issue for Tech Support, but the best they might be able to do is explain why you get that sort of model flaky-ness; I increasingly suspect the fact is that your data fail to support a model with the form of complexity that you want.
... View more