Previously we found that Parkinson's disease (PD) patients are impaired in procedural-based category learning when category membership is defined by a nonlinear relationship between stimulus dimensions, but these same patients are normal when the rule is defined by a linear relationship (Maddox and Filoteo, 2001; Filoteo et al., 2005a,b). We suggested that PD patients' impairment was due to a deficit in recruiting "striatal units" to represent complex nonlinear rules. In the present study, we further examined the nature of PD patients' procedural-based deficit in two experiments designed to examine the impact of (1) the number of categories, and (2) category discontinuity on learning. Results indicated that PD patients were impaired only under discontinuous category conditions but were normal when the number of categories was increased from two to four. The lack of impairment in the four-category condition suggests normal integrity of striatal medium spiny cells involved in procedural-based category learning. In contrast, and consistent with our previous observation of a nonlinear deficit, the finding that PD patients were impaired in the discontinuous condition suggests that these patients are impaired when they have to associate perceptually distinct exemplars with the same category. Theoretically, this deficit might be related to dysfunctional communication among medium spiny neurons within the striatum, particularly given that these are cholinergic neurons and a cholinergic deficiency could underlie some of PD patients' cognitive impairment.