Hi mberwing,
Currently, the template uses the following CSS to change the color of the header and all the colors is from BRAND not use Palettes.
You can change add this CSS code to the Tools > Custom CSS to change the color:
#t4-header {
background: #080808;
}
.t4-megamenu .navbar-nav>li.active>a,
.t4-megamenu .navbar-nav>li.active>.nav-link,
.article-index ul li.active a {
color: #f44941;
}
.t4-megamenu .navbar-nav>li>a,
.t4-megamenu .navbar-nav>li>.nav-link {
color: #fff;
}