White balance can be very tricky, but in normal daylight I find AWB works fine most of the time. You generally get problems in overcast conditions.
If Auto/Cloudy don't do the job then I tend to manually adjust the temperature until it looks right. If there's a white area in the image you can use that as a white point to make the adjustment.
A circular polariser can have awesome affects in these kinds of scenes, but as menioned, you need to be at right angles to the sun. Don't be tempted to use it to full effect or your skies can be too dark.
i clearly have some warmth in the image due to the early AM sunlight, but i'm sure you can see the difference between our shots. i typically set a custom WB prior to shooting, then i also check it in pp.
This shot actually looks way too cool considering it's in early morning, and in addition there seems to be a greenish tint. Obviously I wasn't there so I don't know what you saw, it's just how it appears.
