Unexpected 401 when using NetworkService in Web Service call

When you are calling any CRM Web Service and you decide to specify your own credentials by using a new instance of NetworkCredential, then you should make sure that you are not specifying the 'UseDefaultCredentials' after you have specified the Credentials. This will cause IIS to not fully understand how to authenticate. The result is that you will get this 401.2 error message: Unauthorized: