The Korteweg-deVries (KdV) equation that describes the evolution of nonlinear ion-acoustic solitary waves in plasmas with Kappa-distributed electrons is derived by using a reductive perturbation method in the small amplitude limit. We identified a dip-type (negative) electrostatic KdV solitary wave, in addition to the hump-type solution reported previously. The two types of solitary waves occupy different domains on the kappa (Kappa index)-V (propagation velocity) plane, separated by a curve corresponding to singular solutions with infinite amplitudes. For a given Kappa value, the dip-type solitary wave propagates faster than the hump-type. It was also found that the hump-type solitary waves cannot propagate faster than V = 1.32. (C) 2011 American Institute of Physics. [doi:10.1063/1.3629981]