It turns out that Cisco AnyConnect VPN (through an ASA) doesn’t support NTLMv2. In server 2003 the Default Domain Controller Policy was set to Sent NTLM response only. This has changed from Server 2008 and higher which by default enforces NTLMv2 so if you want to carry on using NTLM authentication with Cisco ASA you will need to modify the Default Domain Controller Policy.

The failures you will see on the ASA and in the DC security log aren’t overly descriptive or helpful:

ASA:

ERROR: Authentication Rejected: AAA failure

DC:

Logon Failure:
Reason:            Unknown user name or bad password
User Name:      username
Domain:            domain
Authentication Package:      MICROSOFT_AUTHENTICATION_PACKAGE_V1_0

The group policy setting you want to modify is: Default Domain Controller Policy\Computer Configuration\Windows Settings\Security Settings\Local Policies\Security Options\Network security: LAN Manager authentication level
Value: Send NTLMv2 response only. Refuse LM
Description: Client computers use NTLMv2 authentication, and they use NTLMv2 session security if the server supports it. Domain controllers refuse to accept LM authentication, and they will accept only NTLM and NTLMv2 authentication.

There are security implications with doing this but it all depends on your environment. You can find more details here: http://technet.microsoft.com/en-us/library/jj852207(v=ws.10).aspx