In the end, I ran up Fiddler (the web browser tool) and accessed the web service in the browser, the header came back telling me that the web service was expecting "Negotiate/NTLM" authentication and I was attempting to authenticate using basic. It now works and here is the code I had to use:
MyWebService service = new MyWebService();
CredentialCache myCredentials = new CredentialCache();
myCredentials.Add(new Uri(service.Url), "Negotiate", new NetworkCredential("MyUserName", "MyPassword"));
service.Credentials = myCredentials;
service.PreAuthenticate = true;
// Call functions etc
Note, I did not require any special certificate code which some people have suggested and this works on an HTTPS connection. I also did not need to specify the domain in the Add() function, just the username and password.