Does your Monte Carlo simulation also compute an approximation to the Jacobian, or are you relying on fsolve's default finite difference approximation (SpecifyObjectiveGradient=false)? The latter is not a good idea when your objective function evaluations are noisy or coarsely accurate. If you cannot supply your own Jacobian calculation, it would be better to use a non-derivative based solver like fminsearch() or ga().
It should also help to apply variance reduction operations of some kind to the output of your Monte-Carlo simulation. Is there any smoothing you can do? Or could you run more random seeds?
Finally, you could loosen the FunctionTolerance parameter (TolFun if you are using fminsearch) to make the stopping criteria more tolerant to random noise in your objective. You could also substitute your own stopping criteria using the OutputFcn option.