OK, that's where i though you were. There is a limit to the number of conditional formatting rules you can create and also to the number of conditions. There is a limit to the number of colors you can use so once you hit too many conditional format rules you'll repeat colors.
The category method assumes you assign the same color to several people and instead of applying colors to addresses, (billy, mark, mary or sue are green and john, jack, rebecca, and donna are blue), you would assign the green category to billy, mark, mary and sue and the blue one to john, jack rebeccap and donna. Then create the conditional format rule for all messages with the green category, show in green and one for the blue category in blue.
In this screenshot, i have two colors, blue and green - messages with the blue category use blue conditional formatting while green has green formatting. You can then use Rules to set the categories on message from specific senders so you don't have to assign the categories yourself and unless you use Exchange server, you shouldn't hit the limits for rules as quickly as you do for conditional formatting.
also, rather than redoing all conditional formatting rules, i'd keep most of the current formatting rules - replacing and merging only what i needed to, to add a new rule. For example, if you have several rules assigning the blue color, switch one to use categories and those addresses plus all new address that should be in blue will be assigned the blue category.