As a simple example, suppose I swap out one container type with another one in the internal code. Both implement the same interface/traits, so the change isn't visible to users. But the time complexity of the container operations are different on the new type, and the user was depending upon the time characteristics of the old container. E.g., deletions are now O(n) instead of O(1). I've violated a user expectation without breaking type safety.

Nice counterexample!

Some examples,

1 - Not all changes can be kept internal, for example adding a new case to an ADT

2 - Internal changes can still alter the semantic of the API, even if from the outside everything still looks the same from the type system point of view

Yes, both are true. 2 is a particularly good example.