We study modulational instability (MI) of plane waves in nonlocal nonlinear Kerr media. For a focusing nonlinearity we show that, although the nonlocality tends to suppress MI, it can never remove it completely, irrespective of the particular profile of the nonlocal response function. For a defocusing nonlinearity the stability properties depend sensitively on the response function profile: for a smooth profile (e.g., a Gaussian) plane waves are always stable, but MI may occur for a rectangular response. We also find that the reduced model for a weak nonlocality predicts MI in defocusing media for arbitrary response profiles, as long as the intensity exceeds a certain critical value. However, it appears that this regime of MI is beyond the validity of the reduced model, if it is to represent the weakly nonlocal limit of a general nonlocal nonlinearity, as in optics and the theory of Bose-Einstein condensates.