Re-installed the software and configured the service to run under an administrative account, the service starts without any error and is still running, but the issue remains.

This is exactly how I configured it, but it doesn't work.
When I log off on the remote PC and try to connect from the other one, I get the "Can't connect" message. To me it looks like the Remote Assistance Service is only running when a user is logged in...

Hello,
I'm facing the same issue and have just sent you a diagnostic file.