I just recreated this problem when doing a recursive chown on a home directory after I had already created a toolbox.
Essentially, there’s a lot of entries under/including ~/.local/share/containers/storage/overlay that must have a user:group of 100000:100000. If these get modified (such as the recursive chown I did), you simply break things.
Perhaps run the below to see if wrong user/group/permissions exist for problematic containers:
find ~/.local/share/containers/storage/overlay -type f -name sudo -executable -print0 | xargs -r0 ls -ld
As for fixing it, you can do surgery within the overlay directory or use the podman command you shared. It’s likely some files/directories will still have incorrect permissions though, so it’s possible there may be some side-effects to that.
I suppose you could also try using getfacl/setfacl to get an ACL dump from a working installation and apply it to a broken installation, but it still may not get you 100% there either.
I’m not sure how OP’s installation got to the state it is, but if a recursive chown was done at any point in time (intentional or not), that might explain things.