You can use the CSS next-sibling selector (+) to achieve this however IE6 won't get the styles.
Do something like the following (colour properties are just for example):
ul ul li { background: darkblue; color: lightblue; }
ul ul li+li { background: blue; color: lightblue; }
ul ul li+li+li { background: lightblue; color: darkblue; }
ul ul li a:hover { color: black; }
Alternatively, you'll have to either apply a CSS class to each subitem going down (talk to the programmer if you're not responsible for that), or do it by adding classes with javascript.
Ideally try to convince them that you can't do it for IE6 but modern browsers will manage fine. As long as the site is still usable the gradient of colours is a very minor loss.