We investigated human learning and generalization of three novel category structures based on eight exemplars in a continuous (9x9) stimulus space. Each category requires attention to both dimensions, but they differ in their organization. Critically, all three category types are matched on within- and between-category exemplar distances. The first category structure conforms to a condensation or information-integration type of problem with two classes separable by a diagonal bound. The other category structures cannot be solved with a linear decision boundary. We found that learners trained on the diagonal bound structure showed significantly better learning and generalization performance. In computational simulations, we found that an exemplar model (ALCOVE) could not account for the observed pattern. We posit that ALCOVE is constrained by the matched distances to learn these category structures at the same speed. Another similarity-based model with different basic design principles (DIVA) provided a good account of the behavioral data.