Hola:
En teoría sería cuestión de leer el color de la celda y cambiarlo por uno alternativo, pero recuerdo que la lectura del color variaba según los navegadores (explorer usa el formato #RRGGBB y mozilla usa rgb(rr,gg,bb)...) por lo que mejor sería usar clases...
<style type="text/css" >
.fondoRojo {background-color: red;}
.fondoAzul {background-color: blue;}
</style>
Y en la celda:
<td class="fondoAzul" onclick="this.className = (this.className == 'fondoRojo') ? 'fondoAzul':'fondoRojo'" >
Saludos
