What version are you running?
I am running 5.02(SR1) with AD Integration and had a similar problem that went on for months, with one user. They got the same error message, whether it was on their PC or on mine. While working on it, he changed his password and low and behold he was able to sign on.
I was actually working a TAC case on it and they had no suggestions as to why suddenly when he changed passwords it worked. He had changed his password a couple of times prior and he was still not able to log in, but one day poof, it worked. The whole time he could sign on to the agent desktop, just not HRS.
So you might try changing your password and then signon to one of the machines and see if it works.
Hope it helps,
Doug