After trying the following without any success (all of which were suggested somewhere in this or related threads in these forums):
• un-checking/re-checking RemoteManagement/ScreenSharing in Sharing Prefs
• downgrading to ARD 3.4
• re-installing Apple Remote Desktop Client 3.5
• messing with Firewall settings
I finally achieved consistent resolution to my Screen Sharing problem by using Disk Utility to Repair File Permissions (and a minor Disk Repair, but I think that was unrelated) on the Mac whose screen I was trying to share.
My final setup has
• Screen Sharing checked in the Sharing Pref pane (and Remote Management unchecked)
• Firewall on in the Security & Privacy Prefs and
• in the Firewall Advanced settings, these two processes: kdc and screensharingd, set to "Allow incoming connections"
Now Screen Sharing is working flawlessly. Hope this saves someone some frustration.