Ok, it didn't work... So I tried the opposite, which was to remove the "Everyone" from the server that did work.

I'm modifying settings for individual shares, so this still allowed me to connect to the machine as Guest and see a list of shares. I then could not open the shares (as expected).

The machine I complained about originally won't even let me connect to it to see the shares, so it seems I can't even get to the point where the recent changes to the security settings per-share will make a difference.

Still stuck.