Well, we figured it out.
It turns out that the two objects in question (one of them actually a Custom Setting) had the
_ character in their names. The display name, not the API name.
So what happened was this: the translation system looked for a translation for the name of these objects, and didn't find one. Instead it took the regular display name. But that had one of the new illegal characters in it, a
_. And so the error was thrown.
Our solution is actually different for the 2 objects:
For the custom object, we just changed the display name of the object.
My Custom Object
For the custom setting that wasn't enough, we're not sure why. It might be because of the Object Name of the custom setting, that must have the
_ char, and maybe the translation is taking from that as well...? Unknown.
Whatever the reason is, the solution was to "translate" the custom setting name.
That however, is easier said than done. No obvious way to do it in the Translation Workbench. So we went into the metadata and modified the
My_Custom_Setting__c-iw.objectTranslation file. It does look like there are 2 values there, one for the name of the custom setting and one for the object.
<?xml version="1.0" encoding="UTF-8"?>
<value>My Custom Setting</value>
<value>My Custom Setting</value> <!--Was My_Custom_Setting-->
So now that works.
What is still unexplained is why we had this problem in the first place. This is not a managed package, and according to the release notes linked in the question, this validation only applies to managed packages.