While the ability to acquire non-linearly separable (NLS) classifications is well documented in the study of human category learning, the relative ease of learning compared to a linear separable structure is difficult to evaluate without potential confounds. Medin and Schwanenflugel (Journal of Experimental Psychology: Human Learning and Memory, 7, 355-368, 1981) were the first to demonstrate that NLS classifications are not more difficult to acquire than linearly separable ones when structures are equated in terms of within- and between-category similarities. However, their evidence is less sturdy than might be expected due to non-standard methodology and low sample size. We conducted a conceptual replication to clarify the behavioral picture and perform qualitative testing of formal models. The behavioral results not only showed a lack of advantage for the linearly separable (LS) structure, but revealed a stronger finding: the NLS structure was reliably easier to acquire. Differences in the relative ease of NLS learners to master certain items yielded evidence for the existence of distinct learner subgroups, one marked by significantly easier (not harder) learning of exception items. Comparing the qualitative fits of leading computational models to the human learning performance confirmed that a pure prototype account, even with contemporary updates, remains incompatible with the data. However, exemplar models and similarity-based models grounded in sophisticated forms of abstraction-based learning successfully account for the NLS advantage. In sum, evidence against a linear separability constraint is redoubled, and the observed NLS advantage along with behavioral patterns seen at the subgroup and item level provide a valuable basis for comprehensive evaluation of competing theoretical accounts and models. [ABSTRACT FROM AUTHOR]