The only thing I can find at MS is the fact that when you edit a color category and use the keyboard to navigate after you've renamed a category (like pressing tab after you typed the name), a space is added to the category name. If this is what has happened, the emails you have assigned to a certain category name (without the space) would no longer have an associated category.
Try re-editing the category. Check to see if there is a space after the category name and if so, delete the space then press enter, then press OK to get out of the category editor (do not press escape to exit the editor).
Other than that, I can't find one danged thing about it at MS Knowledgebase. Perhaps you might have different search criteria than what you've told us.