HI equinesites, and welcome to WebmasterWorld :).
Thanks for posting a code sample, and while Suzy is right that some more information would help pin-point the exact issue, before adding more code, it sounds as if this may be an issue with floats. Recalling that per the recommendations, an element that Floats (9.5)
[w3.org] is shifted left/right along the same line. Subject to the clear property, if there is not enough room for all the elements to fit on one line, the float will "drop" down to the next line until it can fit in the allowed width.
In this case you have the <p> floating right of the next element which is the logo image. <img> is itself floating left of the next element which is <ul>. As there is no element following the ul, the float is redundant. That means that if all the elements were narrow enough to fit on a single line they would appear, from left to right as <img> <p> <ul>. However, you have said that in Safari the <ul> "slides too far up". That makes it sound as if ie8 and ff are "dropping" the <ul> to a lower line, while Safari is calculating there is enough room for the <ul> to be drawn on the same line so that it appears to have slid "upwards".
I'm not seeing a difference between ie8, ff 4 and winsafari5 on the provided code and can't see any reason winsafari would calculate the dimensions differently, so there may be something else in the code affecting this. However, as you want browsers to position the items according to whether they "fit" within the total 1000px width of #header, plus be able to lay out the page correctly without waiting for the image to download, it is good practise to set widths on your elements. That will also help problem-solve as you can adjust the widths to see if that is what is causing the layout difference. Also, try applying a clear (9.5.2)
[w3.org] as well.
And of course, post back with more information if that doesn't provide any clues.