Rollover states

update: I have successfully done rollover menu links with textimage
I don't particularly remember how, but here is the code I put in menu-item.tpl.php which can give you clues to how I did it

<?php

$folks = menu_get_menu();  // get menu system 
$kids = $folks['visible']['2']['children'];  // get list of menu-id kids values from "Menu 2"
$link = menu_item_link($mid);  // get link html


if (in_array($mid, $kids)) {  // do the textimage menu

	$converted_link = str_replace('&amp;', '&', $link);
	$converted_link = str_replace('<em>', '', $converted_link);
	$converted_link = str_replace('</em>', '', $converted_link);
	preg_match('/\<a href="(.*)"\>(.*)\<\/a\>/', $converted_link, $matches);
	$image_link = '<a href="'.$matches[1].'">'.theme_textimage_image('menulink', $matches[2], array(), 'png', $matches[2], $matches[2], NULL, TRUE).'</a>';
	$image_link_ro = theme_textimage_image('menulink_ro', $matches[2], array(), 'png', $matches[2], $matches[2], NULL, TRUE);
	preg_match('/.*src="(.*?)".*\/>/', $image_link_ro, $matches);
	$output = '<li style="background: transparent url('.$matches[1].') no-repeat 50% 12px;" class="link-'. $mid .' '. ($leaf ? 'leaf' : ($children ? 'expanded' : 'collapsed')) .'">'. $image_link . $children ."</li>\n";

} else {  // do the normal menu theme

	$css_id = strtolower(str_replace(' ', '-', strip_tags($link)));
	$css_id = str_replace('&amp;','and', $css_id);
	$css_id = str_replace('!','', $css_id);
	$link = str_replace('">', '">',$link);
	$link = str_replace('</a>', '</a>',$link);
	$output = '<li class="link-'. $css_id .' '. ($leaf ? 'leaf' : ($children ? 'expanded' : 'collapsed')) .'">'. $link . $children ."</li>\n";

}

print $output;



?>

also this css (don't use visibility:hidden; the hover flickers)

#block-menu-2 ul li a img {
	padding-top: 7px;
	padding-bottom: 3px;
	-moz-opacity:0.95;
	filter:alpha(opacity=100);
	opacity: 0.95;	
}

#block-menu-2 ul li a:focus img,
#block-menu-2 ul li a:hover img {
	-moz-opacity:0.05;
	filter:alpha(opacity=5);
	opacity: 0.05;
}

possibly this too if it messes up in ie6

  <!--[if lt IE 7 ]>  
  <script type='text/javascript'>
	  $(document).ready(function() {
		$("#block-menu-2 ul li a").hover(
		  function () {
		    $(this).parents('li').children('a').each(
			 function () {
               $(this).fadeTo("normal", 0.95);
			 }
			);
			$(this).fadeTo("fast", 0.05);
		  }, 
		  function () {
              $(this).fadeTo(5000, 0.95);
		  }
		);
	  });
  </script>
  <![endif]-->

and something like this if you're using PNG

  <!--[if lt IE 7]>  
  <style type="text/css">
    img, a, li, div { behavior: url(/sites/all/themes/zen/iepngfix.htc); }
  </style>
  <![endif]-->

Just be careful using this with the sitemap module - you might need to print out two lots of links - one for the menu and one for the sitemap, and then use css to hide the wrong one, or use php to determine whether you're in the sitemap or not (but I don't know how to do that.. perhaps check the query string).

I have been doing this using my module Textimage Autoinsert - it needs a bit of work (and isn't available for D6 yet) as I've come across bugs on almost every complex use-case I try to use it for - but I'm slowly working through it.
But basically my module allows you to apply a textimage preset to a certain HTML element e.g: all H3 tags with the class 'title', or all 'a' tag with the class 'menu-item', and then another preset for all 'a' tags with the class 'active' - as well as choosing how to do this - whether textimage replaces the text, is a background to the text, or is appended to the text. And all of this is done straight from the Textimage settings page - no PHP code or themes necessary (except to install it in the first place)

Still need your own CSS though, to either make something transparent that is over the top of something else, or to slide a background position around, etc.. your choice. Perhaps when I find time to really crack down on making this an easily usable module I will add a feature to automate this.