TonyPlack's solution for manually editing using Get Info inside of ARD is a nice way to resolve this issue that has been bugging me literally for years.
Apple also has a well-meaning but ultimately unhelpful kbase article here: http://support.apple.com/kb/TS2230
It's unhelpful because it uses the incorrect flag in the systemsetup command. The correct command should be:
systemsetup -setcomputername name
Having this command handy opens the door for creating a function to batch-rename a large group of systems, such as piping in the output of a "scutil --get LocalHostName" command into it (so your ComputerName actually matches up with the Bonjour Name).
Does anybody know who to contact at Apple about getting their faulty kbase article updated?
I have just made a change to my admin computer that seams to have helped.
so as some above or elsewhere have discribed, delete out the computers in All Computers, run a scanner and re-add them.
after doing that,
BACKUP then edit the file /SystemLibrary/LaunchDaemons/com.apple.mDNSResponder.plist
under the ProgramArguments Section, add the string
sudo killall mDNSResponder
Seems that dns and bonjoure have become joined into the mdns service. the above string disables the bonjour part of it. see here http://support.apple.com/kb/HT3789
I hope this continues to work for me and you.