Ich finde den schwarzen Header auch zu krass vom Kontrast her. Probiere es doch lieber mal mit einem sehr dunklen Blau, bspw. #0D1224 . Gefällt mir immer noch nicht so richtig, aber sieht nicht mehr so hart aus.
Was auch gut (IMHO sogar besser) aussah, ist einfach ein weißer Header, wobei dann natürlich die menu-Schrift schwarz (nein, zu krass) oder dunkelblau sein muss.