How do people learn to group and re-group objects into labeled categories? In this paper, we examine mechanisms that guide how people re-represent categories. In two experiments, we examine what is easy and what is hard to relearn as people update their knowledge about labeled groups of objects. In Study 1, we test how people learn and re-learn to group objects that share no perceptual features. Data suggest that people easily learn to re-label objects when the category structure remains the same. In Study 2, we test whether more general types of labeling conventions -- words that do or do not correspond with object similarities -- influence learning and re-learning. Data suggest that people are able to learn either kind of convention and may have trouble switching between them when re-structuring their knowledge. Implications for category learning, second language acquisition and updating representations are discussed.