SharePoint: Cannot connect to database master at SQL Server

Problem

You are trying to configure a new SharePoint instance and run the PowerShell command to build the configuration database, New-SPConfigurationDatabase.  The database is installed as a default instance using all defaults.  When you run this command in an elevated SharePoint Management Shell, an error is returned:

New-SPConfigurationDatabase : Cannot connect to database master at SQL server at <yourdb>. The database might not exist, or the current user does not have permission to connect to it.

Creating an inbound Windows Firewall rule on port 1433 does not resolve this issue.
  

Troubleshooting

1. Verified that the account this command is running under (the SharePoint Setup User Administrator account) has been granted the securityadmin and dbcreator fixed server roles on the backend SQL Server instance.  
2. Granted it the sysadmin role, repeated command, but same error.  
3. Ran the command using the actual database server name, but same error.
4. Checked Windows Firewall on the backend: did not identify anything that appeared to be blocking default port 1433 for inbound connections, but also did not find anything explicitly allowing access on this port.  
5. Configured an inbound rule to allow any access on port 1433.  The repeated command, but same error.
6. Created empty Data Link, configured using database alias, and then tested connection: failed.
7. Tried again using actual database server name and then IP address: both tests failed.
8. Discussed this issue with a systems administrator, as to whether firewall rules are controlled via GPO and whether creating a rule using the standard process will in fact implement the rule. He informed me that, no, rules created using the standard process are not in fact implemented.  
9. He showed how to discover what rules are implemented (Windows Firewall > Windows Firewall with Advanced Security on Local Computer > Monitoring > Firewall). Reviewing this list, found that the the rule created previously was not listed.
10. The systems administrator showed how to update the local GPO using gpedit.msc.
11. Created new inbound rule on port 1433 using gpedit.  
12. Checked the list noted above, but did not find new rule.
13. Discussed with systems administrator who showed how to update local computer with modifications to its GPO: use gpupdate /force in an elevated command shell.
14. Executed this command.  Was prompted that "Certain Computer policies are enabled that can only run during startup.  OK to restart?"  Chose No.
15. Checked list: new inbound rule not found.
16. Restarted server.
17. Checked list: new inbound rule now listed.
18. Created empty Data Link, configured using database alias, and then tested connection: success!
19. Reran command to create new configuration database: success!

Solution

1. Create inbound rule on the farm backend that allows inbound connections on the port used for database connections.  Create this rule in the local computer GPO using gpo editor gpedit.msc.
2. Force the backend GPO to update computer settings.
3. Restart the backend.

References

• Initial deployment administrative and service accounts (SharePoint Foundation 2010)
• Plan for administrative and service accounts (SharePoint Foundation 2010)
• Configure a Windows Firewall for Database Engine Access
• SQL Aliases in the real world
• New-SPConfigurationDatabase
• Administer Security Policy Settings
• gpupdate

Notes

• Some knowledge of Windows Server management was helpful here in being able to ask the systems administrator the right questions so as to obtain useful information.
• This issue applies to all SharePoint versions.
• Thanks to Thomas Vochten for an excellent tip on how to quickly explore database connection issues.