Changing the base 16 colors of a 256-color terminal is still useful. I started overhauling my colors a few weeks ago, and decided that the best approach is to colorize most things using the 16-color palette and adjusting that to look nice, rather than eg setting LS_COLORS to spit out high colors. This gets me immediate results for programs/hosts I haven't customized, and less degradation if I happen to be using a less capable terminal.

Indeed, they are complementary. The basic 16 colors can be configured globally by the terminal which is convenient. 256 colors has to be supported by the particular application but I mostly care about the vim scheme anyway. I have a scheme which uses multiple shades of gray so as not be as distracting as the typical syntax highlighting `salad.'