If you experience difficulty logging on via the web service interface to a CRM Install (that was installed using windows authentication) this can be helped by setting the UseDefaultCredentials flag for the web service client to true.

See highlighted line in the code snippet below.

private static bool LogonToCRMSystem()
{
Write("Please provide the necessary information to Log onto CRM - ");
String userName = ReadUserInput("Please Enter User Name: ");
String passWord = ReadUserInput("Please Enter User Password: ");
String crmInstall = ReadUserInput("Please Enter URL to CRM Install: ");
try
{
binding.Url = crmInstall;
binding.UseDefaultCredentials = true;
SID = binding.logon(userName, passWord);
binding.SessionHeaderValue = new SessionHeader();
binding.SessionHeaderValue.sessionId = SID.sessionid;
return true;
}

catch (SoapException e)
{
Write(e.Message);
if(TryAgain()) // if the wrong password was given allow them to try again.
return LogonToCRMSystem();
}

catch (Exception e)
{
Write(e.Message + "\n" + e.StackTrace);
System.Threading.Thread.Sleep(5000);//give user time to read the message
}

return false;
}

Thanks to my colleagues in Dublin.