Rather than changing the header colour, I'd either have a version of the logo that works in white (and other solid colours). You won't always be in a position to dictate a background colour so your logo has to adapt, not the other way around.
There's a number of issues that could be going on, My first thought is Shopify/your server is compressing/shrinking the image after it's uploaded. If you haven't already, I would try uploading an image at the exact dimensions that's displayed and also try a version that's twice as big to account for retina screens (so 420px x 96px). Try compressing the image using TinyPNG first to get the file smaller so compression during upload isn't needed.
Secondly, the colours are quite jarring due to them using a similar tonal range. The turquoise/yellows particular blend into the background which can give the illusion of an image being fuzzy. Basically use colours that have more contrast and as above, have alternatives for cases when you need a solid dark/light colour.
