The effect of processing type on the process of overriding prior experience and learning restructuring was examined within a categorization paradigm. Participants were trained to categorize either explicitly, implicitly or received no training. Explicit training encouraged participants to use hypothesis-testing while implicit training encouraged categorizing via intuition or gut instinct. Participants then worked on a modified categorization task in which they learned an initial "misconception" category and later had to restructure their representation to learn a target category. Participants were able to successfully learn the misconception and restructure to the target. Data suggest that increased category complexity results in a longer learning period that leads to the generation of a category representation that is more accessible and more readily restructured. The complexity effect is driven by similar performance across the different training types. The experimental and real-world implications for the interplay between stimuli complexity and processing type are addressed.