Every time I've encountered this exact issue, be it with flash-based headers in the skin or menus disappearing behind embedded videos, it's always been fixed by adding the Wmode parameter and setting it to opaque. Depending on the method that the flash is inserted, you may have to edit one or two instances. For instance, the embed code provided by Youtube, Vimeo, etc usually spits out the Object/Embed code which requires the changes be made in both 'parts'. However, I have seen some Javascript functions created to make the embed / insertion code more 'valid' ( ALA: Flash Satay ) . I noted your comment that 'since the flash is the header' you can't edit these parameters. I'm not quite clear on this, is the flash element inserted via a module? Otherwise, you should just be able to modify the skin's ASCX file with the required parameters.

If I've glossed over something, please let me know.

I did gloss over something, the mention that the header is in JS and not flash... for this you should be fine adjusting the Z-index for that selector in the CSS.