The ability to acquire non-linearly separable (NLS) classifications is well documented in the study of human category learning. In particular, one experiment (Medin & Schwanenflugel, 1981; E4) is viewed as the canonical demonstration that, when within- and between- category similarities are evenly matched, NLS classifications are not more difficult to acquire than linearly separable ones. The results of this study are somewhat at issue due to non-standard methodology and small sample size. We present a replication and extension of this classic experiment. We did not find any evidence of an advantage for linearly separable classifications. In fact, the marginal NLS advantage observed in the original study was strengthened: we found a significant advantage for the NLS classification. These results are discussed with respect to accounts provided by formal models of human classification learning.