If you are using Apple Remote Desktop there is a good chance you're using it to control a Mac you don't have ready access to – like a headless server, an OS X machine in a colocation facility, etc. And if you lose ARD access for no reason it can be alarming.
And it does happen. Sometimes ARD will just stop working for a particular machine. The error shows as "Authentication failed to 'client name'", which leads you to think that the problem is with credentials – some kind of username/password error. That leads to trying out every combination you can think of, often forgetting what the correct settings were in the process.
There are some other fixes discussed online. Some people suggest physically accessing the remote machine and changing the sharing preferences – turning remote management permissions on and off. That did not work for me, even with multiple tries and, since that requires the kind of physical access you may not have it should really be considered as more of a last resort.
Other fixes suggest reinstalling aspects of the ARD client software but those were time consuming and tricky and, again, they didn't work for. Consider skipping ahead to a simple solution that does seem to work reliably, and does not require physical access.
1. Open up Terminal and connect to the machine that you cannot reach via ARD. Since by this point you have likely tried MANY different username/password combinations use the Terminal login as an opportunity to determine the correct credentials.
2. Paste the following line into Terminal and hit Return:
sudo /System/Library/CoreServices/RemoteManagement/ARDAgent.app/Contents/Resources/kickstart -activate -configure -allowAccessFor -allUsers -privs -all -clientopts -setmenuextra -menuextra yes
That's it. This is one of several commands that is part of the the kickstart command-line utility in Apple Remote Desktop, and it seems to be the fastest and easiest way to solve the ARD "Authentication failed to...: error.