One somewhat subtle implication is that you need to have a clearly defined expected behaviour. If people have to read your implementation to use your API, then your implementation has become the specification and basically every change will be a breaking change.
Basically, if your old unit tests break, or if the post-conditions changed (in case you use design by contract), that's a new major version, otherwise, it's not.
But yeah, there are counter-examples, and anyway a user can expect a behavior to remain even if it is not explicitely specified. For instance, I developed a SAT solver. I could make a non-breaking change that improves the efficiency of the solver in like 99.9% of the cases, because of a cool heuristic. That would be considered a "patch", since I didn't change the API at all, and all unit tests are still working perfectly. But a former user could be pissed off because he's part of the 0.1% and now the tool became just a little too slow for his use. Is that a breaking change or not?
