Locked sign here means that the remote computer is visible (say, you can ping it's IP address), but you are not logged on. By being "logged on" I mean logged on using the LogOn feature in Remote Utilities, not Windows logon.
Thank you for that comment [maybe that sentence should be in the manual?]. It allowed me to focus on what it might be. Turns out my second host was working fine today [even though I made no changes overnight], so i simply looked for differences between the two hosts and local settings. Found that one host had security > confirmation > 'ask user permission' ticked. Unticking this made it work.
Mind you I only tried ticking various buttons yesterday because neither host were working. I only changed settings in one of them though, which is lucky as the other one suddenly works fine today. So I presume there was a problem yesterday that magically fixed itself overnight [restarts of all machines and networks maybe?].
In any case I am now happy :)