Danny, while I do not understand everything you are doing, here are my thoughts based on what you said in this forum.
1. The sqp algorithm is usually superior to the active-set algorithm, in that it is more robust and it respects bounds.
2. The interior-point algorithm is probably the most robust algorithm, and usually you should try it first, resorting to the others only if it proves unsatisfactory.
3. It is often crucial that you take a good starting point for the minimization. Especially, if you have an inner loop containing other minimizations, you might want to take the answer from one minimization as the starting value for the next.
4. Unlike Shashank, I would never attempt to use fminsearch or any of its relatives on a problem with more than 4 or 5 dimensions. It is almost always better to try to tune fmincon than to use a much poorer algorithm. You could try patternsearch, but it would likely be slower than fmincon (when properly tuned).
5. The best thing you might be able to do for fmincon would be to figure out somehow analytic gradients for the objective and nonlinear constraints, or some good approximation to them, and use them instead of letting fmincon take finite difference steps.
MATLAB mathematical toolbox documentation