pounder. There's lots of ways to skin this cat. One (without checking my code, so excuse any typos, is)

<ul id="MainMenuHolder">
....
<a href="...." class="menu_$ID">
....
</ul>

and then your css have

.MenuHolder A { default menu style }
#menu_home {}
#menu_about {}
#menu_contact {}

You could even make a new field inside the CMS, like "menutheme", and this might be a text box, or a dropdown, and thereby specify "red" or "blue" in terms of values, which you use in the same way as my code above... either defining exact CSS classes, background images, etc.