Me alegro de que lo hayas solucionado, pero me sorprende lo de que
a.nuevaclase:link es incorrecto

He hecho un ejemplo sencillo y parece que funciona bien:
Código:
<html>
<head>
<style type="text/css">
a:link {color:red}
a.link2006:link {color:green}
</style>
</head>
<body>
<a href="algo.html">Enlace</a>
<a href="algo.html" class="link2006">Enlace</a>
</body>
</html>
Saludos,