ISA/TMG installation fails with Unable to Connect to configuration Storage Server

While installing ISA or TMG Enterprise Edition the installation might fail with the following error

Setup failed to connect to the specified configuration storage server computer. This may be because the local computer needs to be added to the Replicate configuration storage server computer set. Error code = 0x8007203a

On TMG the error will look like this