The Upgrade to Color Categories feature doesn't work as expected in Outlook 2013. When you open an existing .pst or import categorized items into Outlook 2013 and run upgrade to color categories, the categories are not added to the Master category list.
You have two options to add the categories to the master list:
If you have a list of the category names, you can use a macro to add them to the list. See Create a list of color categories and merge or restore the list using VBA for details and the necessary macro code.
You can select an item that has one or more categories not in the master list, click Categorize button, then select All Categories to open the Color Categories dialog. Select a category that is not in the master list then click New.
This will open the new Category dialog with the category name entered and a random color assigned. Change the color and assign a shortcut key, if desired.
Click OK to add the category to the list. Repeat for each category that needs added to the list.
Using Upgrade to Color Categories
To use Upgrade to Color Categories in Outlook 2007, 2010, or 2013 (when it works), right click on the top level of the data file and choose Data File Properties. Click Upgrade to Color Categories…
Published August 16, 2013. Last updated on August 16, 2013.