Categories are stored in the computer's registry, in a key like
"HKEY_CURRENT_USER\Software\Microsoft\Office\8.0\Outlook\Categories", the
numeric value in the key (8.0 in my example) depending on which version of
Office you're using, and the upgrade should have left them there.