CRM 4.0 - Login fails 'Key Expired'

On our CRM Production environment I experienced the following:
When one of the User opened CRM, the below message appeared:

The key specified to compute a hash value is expired, only active keys are valid. Expired Key : CrmKey.........


After some research I found that the CRM Async Service wasn't running, which when started solved the issue.