Struggled with this one a lot yesterday & google was not much help other than finding others running into the same confusion.

I could browse the wsdl just fine in IE, so IE was passing credentials just fine. So after like 5 hours of "wtf" decided that the add reference for discovery dialog in VS2010 just was not passing credentials.... evidenced by the error msg indicating the server doesnt permit anonymous authentication....