Hi,
Do you mean this issue also doesn't happen with Outlook 2010 before upgrading to Windows 8?
Which type of email account are you using? POP3, IMAP or Exchange? Please note that categories are not supported by IMAP protocol. Maybe you were using another protocol (such as POP3) to configure your email account in Outlook before upgrading to Windows 8. If this is the case and you need to use categories, you need to use a POP3 account instead or move the messages to a local pst file.
If I've misunderstood something, please feel free to let me know.
Regards,
Steve Fan
TechNet Community Support