Установите учетные данные веб-службы в System.Net.CredentialCache.DefaultCredentials в вашем консольном приложении
MyWebService proxy = new MyWebService();
proxy.Credentials = System.Net.CredentialCache.DefaultCredentials;
Редактировать
передать учетные данные программно:
MyWebService proxy = new MyWebService();
proxy.Credentials = new System.Net.NetworkCredential("username", "password", "domainname");