Hi, we needed the diferent color tabs, and we use your idea but with some modification. Hope it works for some people:

<SharePoint:AspMenu
  ID="TopNavigationMenu"
  Runat="server"
  DataSourceID="topSiteMap"
  EnableViewState="false"
  AccessKey="<%$Resources:wss,navigation_accesskey%>"
  Orientation="Horizontal"
  StaticDisplayLevels="2"
  MaximumDynamicDisplayLevels="1"
  DynamicHorizontalOffset="0"
  StaticPopoutImageUrl="/_layouts/images/menudark.gif"
  StaticPopoutImageTextFormatString=""
  DynamicHoverStyle-BackColor="#CBE3F0"
  SkipLinkText=""
  StaticSubMenuIndent="0"
  CssClass="ms-topNavContainer">
  <StaticMenuItemStyle CssClass="" ItemSpacing="4px" />
  <StaticSelectedStyle CssClass="ms-topnavselected" ItemSpacing="4px" />
  <StaticHoverStyle CssClass="ms-topNavHover"/>
 <StaticItemTemplate>
  <div class="<%# GetMenuItemClass(Eval("Text").ToString())%>" style="height:100%">
   <a href="<%# Eval("DataPath") %>">
    <%# Eval("Text") %></a></div>
 </StaticItemTemplate>
 <DynamicMenuStyle  BackColor="#F2F3F4" BorderColor="#A7B4CE" BorderWidth="1px"/>
 <DynamicMenuItemStyle CssClass="ms-topNavFlyOuts"/>
 <DynamicHoverStyle CssClass="ms-topNavFlyOutsHover"/>
 <DynamicSelectedStyle CssClass="ms-topNavFlyOutsSelected"/>
</SharePoint:AspMenu>
<script runat="server" type="text/C#">
 private string GetMenuItemClass(string nombreP)
 {
  string cssClass, lists, name, style, temp;
  cssClass = System.Configuration.ConfigurationSettings.AppSettings["cssDefault"].ToString();
  list = System.Configuration.ConfigurationSettings.AppSettings["ListSHP"].ToString();
  SPWeb web = SPContext.Current.Site.RootWeb ;
  //SPWeb web = SPContext.Current.Web;
  SPListItemCollection items = web.Lists[list].Items;
 
  foreach (SPListItem item in items)
  {
   name = System.Configuration.ConfigurationSettings.AppSettings ["TabName"].ToString();
   style = System.Configuration.ConfigurationSettings.AppSettings["TabStyle"].ToString();
   if (item[nombre].ToString().ToUpper() == TabName.ToUpper())
   {
    cssClass = item[style].ToString();
    break;
   }
  }
 
  return cssClass;
 }
</script>

The idea is to use a SharePoint List to manage the styles of the tabs.

So, we have a SharePoint List with two fields one with the name of the tab and other with the colour wanted for each tab. you have to create the style that you want to apply to each tab.

we have themes for each site, so in each theme.css we add the default styles for each tab in our case:
 

.green{
 border-color: #428914;
 border-style: solid;
 border-width: 1px 1px 0px 1px;
 background-image: url("topnav_green.gif");
 background-repeat:repeat-x;
 background-color: #F0F8E7;
 color: #428914;
 font-size: 11pt;
 font-family: Arial;
 vertical-align:middle;
}
.green a{
 color:#FFFFFF;
}
.blue{
 border-color: #0073BA;
 border-style:solid;
 border-width: 1px 1px 0px 1px;
 background-image: url("topnav_azul.gif");
 background-repeat:repeat-x;
 background-color: #E3EAF5;
 color: #0073BA;
 font-size: 11pt;
 font-family: Arial;
 vertical-align:middle;
}
.blue a{
 color:#0073BA;
}
 
 
and the hover and selected depends of the theme that you have on the site that you're viewing
 
thanks Mahdi!