Authentication error querying Dynamics CRM OrganisationService

An IIS website we had that queries the Dynamics CRM (2011) OrganisationService was getting

”[SecurityNegotiationException: The caller was not authenticated by the service.]“

Thrown back at it when being accessed under certain circumstances (I forget exactly what they were, although I do remember it being a huge pain in the butt). The Service was instantiated using CredentialCache.DefaultNetworkCredentials as in many examples. The problem was that those client credentials were not being impersonated correctly even though impersonation and windows auth was enabled in IIS.

Turns out the solution was to add an
[OperationBehavior(Impersonation = ImpersonationOption.Required)]
attribute to any methods that tried to query the OrganisationService!