Restarting an ArcGIS Data Store machine on AWS causes entries in the pg_hba.conf file to be dropped, not allowing connections to the Data Store for publishing.
Manually add the entries to the pg_hba.conf file using the allowconnection command, pulling the appropriate database name and username from the listmanagedusers command.