SharePoint 2013: the database name is not a valid configuration database

Problem

You are adding another WFE to your existing SharePoint 2013 farm. You've configured the machine; installed the prerequisites; and installed the binaries.  You now run the Products Configuration Wizard, but then experience this error:

Checking the server's Application log, you see these events:

Log Name:      Application
Source:        Microsoft-SharePoint Products-SharePoint Foundation
Date:          [datetime]
Event ID:      3759
Task Category: Database
Level:         Error
Keywords:      
User:          [FarmAdministrationAccount]
Computer:      [WFEBeingAdded]
Description:
Database '[DB name or alias]' on SQL Server instance '[Alias]' is not empty and 
does not match current database schema.
Event Xml:
...

and

Log Name:      Application
Source:        Microsoft-SharePoint Products-SharePoint Foundation
Date:          [DateTime]
Event ID:      5586
Task Category: Database
Level:         Error
Keywords:      
User:          [FarmAdministrationAccount]
Computer:      [WFEBeingAdded]
Description:
Unknown SQL Exception 10060 occurred. Additional error information from SQL 
Server is included below.
A network-related or instance-specific error occurred while establishing a 
connection to SQL Server. The server was not found or was not accessible. 
Verify that the instance name is correct and that SQL Server is configured 
to allow remote connections. (provider: TCP Provider, error: 0 - 
A connection attempt failed because the connected party did not properly 
respond after a period of time, or established connection failed because 
connected host has failed to respond.)
Event Xml:
...

and

Log Name:      Application
Source:        Microsoft-SharePoint Products-SharePoint Foundation
Date:          [Datetime]
Event ID:      5617
Task Category: Topology
Level:         Error
Keywords:      
User:          [FarmAdministrationAccount]
Computer:      [WFEBeingAdded]
Description:
SharePoint object [SPConfigurationDatabase] is in an unsupported state, and 
could not be used by the current farm. 
Event Xml:
...

Solution

1. Exit the SharePoint Products Configuration Wizard.
2. Install all CUs up through your farm's current patch level (March 2013, December 2013, etc). Note: the March 2013 CU must be installed first prior to installing any of the subsequent CUs.  This does not apply if you are installing SP1, which does not require the March 2013 CU and is fully self-contained.
3. Re-run the SharePoint Products Configuration Wizard.

References

1. SharePoint 2010 Installations: Adding a second server to an existing SharePoint Server Farm
2. SharePoint in a 3 Tier farm
3. Updates for SharePoint 2013

Notes

• I verified that the farm administration account was mapped to the configuration database as dbo.  Thus, at least in this case, the cause for this problem did not involve permissions.  But note that incorrect permissions can result in the same error message (see reference 1).