En realidad si utilizas setAttribute("class", "...") en IE (6) no te funcionará pero si en Firefox. En cambio si colocas setAttribute("className", "...") te funcionará en IE pero no en Firefox.
La solución para ambos sería poner document.getElementById("idElemento").className=". .."
Y esto es puramente JavaScript; AJAX no entra en juego en ningún momento (
http://es.wikipedia.org/wiki/AJAX)
Saludos.