Viewing other user’s default and custom categories in Outlook 2007 public folders must have the same category name. By default, Outlook 2007 has six default color categories named: red category, blue category, green category, etc.. At a customer site, users had been marking tasks in a public folder indicating who was working on which e-mail. One user created new custom categories (ex. John Doe's Tasks) and assigned it a color, then deleted the “red category” default category. When she removed the default categories, she could no longer see what anyone else had marked nor could they see her new category markings. [more]
In order for all users to see custom category names, each user must have the same exact category name created in their category list. You can re-add the default categories back in by creating new ones and naming it back to the default (ex. red category). Color assignments do not matter, only the name.