The error we were getting was:
CloudLink - The current account doesn't have sufficient privileges to give 'Logon As Service' privilege to the selected account. An administrator will need to manually allow this account to run as service. Failing to do so will prevent the service from running.
The problem? Good old User Account Control or UAC for short.
After trying again by running ArchiveTools CloudLink as "Run as Administrator" the problem was resolved.