Thank you, Quinn. I attempted to run the store-credentials but got a confused. It asked me for the Path to App Store Connect API private key. I didn't have one of those. So I attempted to create a new key here:
https://developer.apple.com/account/resources/authkeys/
To make a long story short, this led me down the wrong keygen rabbit hole. After some more poking around I found this page:
https://appstoreconnect.apple.com/access/integrations/api
Success. store-credentials accepted the key which I created there, and created a new keychain item which works with notarytool submit. Problem solved.
Except to understand why. As you can see from my screenshot, the old keychain item wrapped a password (which was 19 characters), with a name. The new keychain item is much more complex. Its Name is com.apple.gke.notary.tool, Account is le.gke.notary.tool.saved-creds.MyName and its Where is appStoreConnect. Most intriguingly, when I click Show password, and enter the keychain password, nothing happens.
So maybe the problem was that the current version of notarytool no longer accepts my old-style simple password keychain item. It now requires this fancy item which based on a private key that Keychain Access can't show me. Is that more or less what happened?