I have had this problem today where my Cisco Anyconnect VPN stopped working. It was working all fine until my home broadband hung and rebooted itself. I restarted the PC but Cisco Anyconnect won't come up. I was having errors like "VPN Service is not available. Exiting", "Lost connection to Cisco VPN Service. Restart application". When I went into Services > Cisco AnyConnect Secure Mobility Agent> it was stopped. I sarted it but it went down again in few seconds. It came up and then went down again as if in a loop.I searched the whole internet where I can find a solution to this problem but none of the tips worked for me. I even restored my PC a week back but had no joy. Same VPN service issue and Anyconnect complaining that it has lost connection to VPN service. This is how I resolved the issue and I thought to put it here so someone else don't waste hours like I did to find a solution:
1) Un-install Cisco AnyConnect VPN
2) Unistall any registry cleaner softwares like CCleaner, Lenovo Rapid Boot etc.
3) Make sure the Cisco AnyConnect adapter has disapperared from Device Manager > Network Adapters
4) Delete the folder C:\Program Data\Cisco\Cisco Anyconnect Secure Mobility Client
5) Restart PC
6) Install Anyconnect Software
7) Restart PC
8) It should work as normal now
and after searching almost everywhere on internet this is how I resolved the issue.