It’s important to note that the verbiage of the error may differ, however the root error will be the same. All Aliases Have Failed is the root error message.
To resolve, ensure that all gateway servers available in the service provider infrastructure can communicate with the tenant(s) repository, as well as the SP Veeam Server.
For communication route reference:
As a note, private gateways are not recommended, and is one of the more common scenarios to encounter ‘All Aliases Have Failed’. Veeam will attempt to load balance across any available gateway, based on current tenant connections, and a gateway usable by a specific tenant can get selected, resulting in this error. In addition, a private gateway can introduce a 4 minute and 15 second delay on every task (disk) processed by a tenant.