Windows will cache negative permissions matches. Other SMB clients may as well. Try rebooting every computer and try again now that you've added the "Everyone" setting.
So this is assuming that my most recent changes to "Security" may work, right?
To tell you the truth, I don't even know why the two machines differ in that regard, since I don't recall ever having edited the Security settings on either, only the Sharing prefs.
I did forget to mention (though I suspect it might have been obvious) that Simple File Sharing is not enabled on either machine. I'll be posting another message about some additional differences I've found on these machines from a UI perspective in Explorer.