Yes and no. Potential screen resolution of your viewing audience should determine the size of your layout. There are still 15% to 25% of monitors out there set at a 800 X 600 pixel width/height (depending on who you talk to). A majority are set at 1024 X 768. also with the advent of widescreen laptops you are looking at 1280 X 800 screen resoulution or higher.
This means that as far as width, you should probably keep your headers (and overall layout) at somewhere between 750 and 800, but you could probably get away with 850 to 900 without peeving off too many people. Most major websites still have layout widths of 750 to 800 unless they use a "floating" width which is set as a percentage rather than a fixed number of pixels.
As far as the overall height here are some things to keep in mind...
A good rule of thumb is to experiment with keeping the most important information of your website "above the fold" meaning, if there is something your REALLY want them to see, make sure they can without having to scroll down to see additional information.
I usually go about 450 to 500 pixel in height for the overall layout with "above the fold" content. Of that 450 to 500, I usually don't go over 150 to 175 pixels for a graphic header. However, websites are like snowflakes; no two are exactly alike, so you shouldn't let a fixed number limit your creativity.
A lot of the space needed for your header will be determined by the information your need to have at the top. Some clients will want a biger logo at top or every phone number, mailing address, and email address they've ever had. Site navigation also usually appears at within the header in more conventional design. Readability, usability, and creative presentation all factor into what needs to be in the header, so keep an open mind.
Also, don't forget to look at your page in multiple browsers at multiple resolutions and try to find a happy medium that satisfies the client and audience.
Hope this helps!