Hola
Sintácticamente tienes un serio error y es incluir elementos de bloque dentro de un inline. Esto, entre otras cosas, genera comportamientos que no solo no son lo que deseas, si no que pueden variar de navegador a navegador.
Sin embargo, si cambias los div's por spans, tendrías un código correcto y siguiendo el ejemplo que te dejo, te funcionará bien, al menos en firefox, opera, konqueror y safari.
Código HTML:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
<style type="text/css">
* {background-color: #000; color: #fff;}
html {background-color: #cf112e;}
body {background-color: #c1f12e;}
.link:hover span{ background:#FF66CC; }
span {display:block;}
</style>
<script type="text/javascript">
</script>
<title>Pruebilla</title>
</head>
<body>
<ul>
<li><a class="link"><span class="01">Titulo</span><span class="02">Texto</span></a></li>
</ul>
</body>
</html> Felicidad