You will have to be creative.
I recommend simply editing the category descriptions to include some colorful HTML. It won't change the color of the entire category bar, but it can easily set apart the different categories with colors inside of that bar.
Otherwise I can imagine some template code that references different background gradients based on node_id, but that is a little yucky.