LsClient does not perform any actual scanning, so it is normal for LsPush scans to take longer. A minute does seem unusually long however.
Could you try running LsPush manually on one of the affected machines.
- First, run it with the /file parameter and see how long it takes for the scan to complete.
- Then run LsPush with direct server connection and the /showresult parameter to verify how long it takes for the server connection to be established. You will receive feedback as to whether or not the connection succeeded.