Cambiar color css

Hola

Efectivamente, puedes hacerlo con CSS y colocando el código en algún archivo CSS de tu theme
Sin embargo te recomiendo que si vas a estar haciendo cambios de este tipo antes desactives los parámetros de optimización CCC y cache, desde Parámetros Avanzados > Rendimiento.

Prueba con el siguiente código CSS:

.shopping_cart > a:first-child,
header .nav{
    background:red;
}

PD. Revisa si tu sitio carga algún archivo customuser.css o similar que sería el archivo correcto en donde deberías agregar cambios. Actualmente no te puedo confirmar ya que tu código esta optimizado.

Saludos.