For anyone that uses it, here's today's word of warning for ARD. (Apple seems to be on a quest to break this software in some horribly weird and hard to troubleshoot manner, a treat they visit on many large institutions about once a year it seems)
If you install Apple Remote Desktop on a computer whose software is up to date, it won't run properly. It can be connected TO, but you'll get the usual mess of "offline", "authentication failed", and "Authenticating" when trying to connect to clients that you've come to expect periodically.
This time the problem is the 3.9.3 client update. If it's already on the machine when you install ARD 3.9, it will backtrack the .3 update and break OUTGOING connections. (the client is broken, which somehow breaks the server, not the client) This isn't unusual, the ARD admin has contained the client since version 1.2 or so and is OCD about overwriting whatever you have with what it contains when you first launch it
Anyway, the fix is to get the 3.9.3 client components reinstalled. Even though it's now back at 3.9.0'ish, software update won't notice this. You will need to download the 3.9.3 client updater from Apple's web site and run it. That will immediately get ARD working again on that computer. Mercifully, relaunching ARD doesn't trigger it to overlay the 3.9.0 components again. But I suppose that's why nobody at Apple noticed the problem, because it only bites new installations, not existing ones. (in the past I've had to hard lock the files to prevent the admin from overwriting them and breaking itself in the process on every launch)