That is because a first-order approximation approximates exp(x) with a linear function exp(x_ss)*(x-x_ss), where x_ss is the steady state. Of course, a linear function will always hit negative values with some probability (as long as its slope is not 0). Using a second-order approximation means fitting a parabola to exp(x), thus preserving some of the curvature. This may avoid having negative values if the vertex is above 0 (but for extreme shocks does not preserve monotonicity of exp(x)).
These problems are always associated with using approximations and are usually accepted. Negative values should be rare and should be thought of as approximation errors.