Ayer estuve hasta las 4 de la mañana rezando a San Peleponosio para que me iluminara, pero deberia de estar ocupado, no me hizo ni caso

...
Bueno, este es mi problema y gratificaré con un viaje a Mexico para 2 personas con todos los gastos pagados a quien me ayude:
1.- Extraigo una serie de datos de una BD (Fácil hasta ahora)
2.- Los presento en una tabla (Esto esta chupao)
3.- Estos datos se pueden ordenar haciendo cilck en cada cabezera, de esta forma si el usuario desea ordanarlos por categoría, por orden alfabético según el título, por fecha, etc... lo puede hacer, simplemente el click es un link que arrastra una variable (Sigue siendo fácil, ya lo sé)
4.- EL MEOLLO: Mi problema es que quisiera que cada fila de la tabla se mostrará de un color según la categoría a la que pertenece el resultado.
Me experiplico: Imaginaos que se muestran 10 resultados, 3 de ellos pertenecen a la categoría A (Las categorias tambien son dinámicas), 2 a la categoría B y 5 a la categoría C.
Entonces lo que necesito es que todos los que sean de la categoria A vayan en fondo rojo, los de B en verde y los de C en color caquita por ejemplo...
Pero que cuando un usuario ordene por ejemplo por fechas, aunque los resultados se muestren salteados en cuanto a que ya no estan ordenados por categorias, mantengan el color del fondo según la categoría a la que pertenecen...
Joder, ya me se ha hecho la picha un lio, si alguien me ha entendio y puede explicarme como resolverlo de forma sencilla y con algún código que me dé pistas le quedaré eternamente agradecido y juro que si en mi próxima reencarnación me convierto en tigre, no me lo comeré...
Gracias compadres!!