After further experimentation, I have now found the answer:
On one connection, the Verification was working fine... so working through the "Distributed Testing - Requirements" pages in the TestComplete Help, I compared all the settings between the working connection and the not-working connection.
The Restrict each user to one session option on the Terminal Services Configuration was set to Yes on the working connection, but was set to No on the not-working connection.
I changed it to Yes... and the verify then works!
The "...is not logged in on the slave computer" error is not mentioned on the "Message - Verification Failed" help page so perhaps that could be tweaked to point towards checking the Restrict each user to one session detail?
(Since I sorted it out, I have now also been able to run Jobs in a Distributed Test style... Everything is working well.)
