As much as I love ARD, Microsofts RDC is much much faster or at least much more bandwidth efficient. I can control several PCs at once over ADSL with RDC, ARD usually requires me to switch to black & white to make it usable. My suspicion is that the clients internet connection is ultimately the problem but of course it used to work fine before the Mac went in and they were remotely accessing a PC.
I have't tried Litemanager though, I'll go take a look thanks.