Configuration Failed - Failed to connect to the configuration database: Error during decryption. Ensure the passphrase is correct.

Problem: Trying a add a server to SharePoint 2013 farm, after a passphrase reset. Got this error message.
Configuration Failed
Failed to connect to the configuration database: 
An exception of type System.ArgumentException was thrown. Additional exception information: Error during decryption. Ensure the passphrase is correct.

Troubleshooting:

• Double-checked my pass phrase is correct. If my pass phrase is wrong, I should get this error message: "The passphrase you entered is incorrect. Please try again" - But I didn't receive any such!
• Verified the pass-phrase change timer job's last run time:
  

  Get-SPTimerJob -Identity job-admin-passphrase-change | Format-Table -Property DisplayName,Id,LastRunTime,Status

• Tried restarting SharePoint Timer job and SharePoint Administration services in CA server
• Made sure the account I logged in is a Farm Admin account with Security Admin, DB Creator roles in SQL Server and Local administrator in the server I'm trying to add.

Solution Worked for me:
Clear SharePoint Configuration Cache on ALL SharePoint servers! and rerun the configuration wizard in the new server!! Here is how: How to Clear SharePoint Configuration Cache using PowerShell