Okay, completely out there answer from me. I was getting this error from a development environment hosted on VM VirtualBox. Three servers; SharePoint, SQL DB and Domain Controller. The SharePoint server couldn't connect to the configuration database. I could still connect via ODBC for Sql authentication using SA account but not Windows authentication. But that user would happily log into SSMS on the sql server itself. I got a better error message from ODBC too and also by checking the failed login messages on sql server:
select text from sys.messages where message_id = '18452' and language_id = 1033
Can't take credit for this because I asked one of our Enterprise Systems Administrators for help and he diagnosed it in about 5 minutes of looking at a few screen shots I sent him. Problem was that the Domain Controller’s clock was set incorrectly! Couldn't believe it. The servers are setup for Host Only networking so don't have internet to sync the clock with. That also explains why rolling back to an earlier snapshot when I know the system was working didn't solve the problem.
Edit: Installing the Guest Additions on the server syncs the guest clock with the host.