lsqnonlin is a gradient-based solver. It first attempts to estimate the local gradient by small finite difference steps. If your function is locally constant, such as a step function, then lsqnonlin sees zero gradient and stops.
To have your function not look like a step function, perhaps you can interpolate it using interp2, for example.
MATLAB mathematical toolbox documentation