Thanks to Matt Otto who figured out that I need to update WSDL file to the one available at http://weather.gov/forecasts/xml/DWMLgen/wsdl/ndfdXML.wsdl. I posted updated archive here. Now I can see Redmond weather forecast for the upcoming week. Guess how does it look like? You betcha...

Updated version: http://blogs.msdn.com/mikhailarkhipov/archive/2006/06/12/628540.aspx