Another way to do it is to add special class to each li in the list.
In /template/catalog/navigation/left.phtml
replace the foreach with this:
<?php $i; foreach ($_categories as $_category): $i++; ?>
<?php if($_category->getIsActive()): ?>
<li clas="colour0<?php echo $i; ?>">
<a href="<?php echo $this->getCategoryUrl($_category) ?>"<?php if ($this->isCategoryActive($_category)): ?> class="current"<?php endif; ?>>
<?php echo $this->escapeHtml($_category->getName()) ?>
<span class="count">(<?php echo $_category->getProductCount() ?>)</span>
</a>
</li>
<?php endif; ?>
<?php endforeach ?>
What I did is adding a new class to each LI which you can rename to whatever you would like and in your css you need to add colour to each class:
.colour01:hover {background:#000}
.colour02:hover {background:#fff}