It could happen if your objective function is piece-wise flat (and hence non-differentiable). fminsearch is a derivative-free solver, so it is less vulnerable to this, but a piece-wise flat objective is best avoided.
t=linspace(-5,5,1e6);
fun=@(x) interp1(t,t.^2,x,'nearest'); %piece-wise constant
tmin=fminunc(fun,3.5)
tmin=fminsearch(fun,3.5)
However, now let's make the objective smooth:
fun=@(x) interp1(t,t.^2,x,'cubic'); %smoothed version of previous objective
tmin=fminunc(fun,3.5)
tmin=fminsearch(fun,3.5)
