Outlook 2007: Adding/changing Color Categories
To change or add color categories you first can either right click on the toggle button in the e-mail description or select the categorize tab after double clicking on the e-mail to open it in a separate window. Then select All categories.
From here you can make new categories, rename existing ones and select the color to be displayed. You can also define shortcut keys to assign the categories.