I have no opinion about this particular change, as I haven't looked into it much and I haven't done any Java in a while. I'm just pointing out that there is something of an implicit time complexity guarantee with any API, so the lack of an explicit API contract isn't enough to say that code which breaks due to a change is at fault.
If your argument is that the String implementation change constitutes "unreasonably poor performance," as in...for most normal use cases, then that makes sense. I disagree with it, but it makes sense to argue that if you think that is what's happening. That goes beyond the implementation vs. contract discussion, and maybe that is the real issue many people have. Maybe some feel like the performance hit will affect so many use cases that are common for String, that it is an unreasonable performance change.