The issue was a symlink in my app: The Info.plist points to a file for the app icon. That file is a relative symlink to an existing icon file. This used to work for many years, and the Finder has no problem with it, either. Just Apple's recent verification process stumbles over it, without sending an error msg about it to me.

To anyone filing bug reports: Please leave a copy at https://openradar.appspot.com/ so that others can see what the problem is you reported.