"Returns a new string that is a substring of this string..."
Both implementations satisfy the API description so the API didn't change, the implementation did.
Optimizing your code based on the internals of a supposedly opaque data structure is a bad practice and if you get burned you only have yourself to blame.
You inescapably either:
1 - substring introduces a new string, creating lots of garbage since it's an incredibly common operation,
or
2 - substring saves garbage in many cases by having substring return sub-chunks of the full char array, but you will be unable to gc the full string as long as any substring remains reachable
The end-game for what you're suggesting is that all Java developers who care about performance, and do heavy string manipulation in their performance critical code, should re-implement the String class. I do not find that realistic.
That means that if there's no explicit running time guarantee given, your alternatives are to either not use that API at all, or depend on the running time you can observe or guess at.
Since people write APIs to be used, the former is obviously not what's intended. So it's pretty reasonable to consider any API without an explicit running time guarantee to have an implicit one along the lines of "this won't get vastly worse" because your only other choice is not to use it at all.
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.
For the record, C++'s standard library has algorithmic complexity as a part of the API. See the analogous std::basic_string::substr: http://en.cppreference.com/w/cpp/string/basic_string/substr
I've been bitten by std::list::size in pre C++11 code, as it was allowed to be O(n). But they were clear about it, the fault was mine. Now, it is guaranteed to be O(1): http://en.cppreference.com/w/cpp/container/list/size
I think it's likely that the change to String.substring was actually a good one. But I also agree with others that it was rolled out poorly, and should probably not have been in a fixpack release, as from how I see it, they changed the API.