There's always going to be corner cases. Fortunately, there is always a person available to act as a referee.
Well, that and the Pirate Code: "The Code is more what you call guidelines, than actual rules...."
If the bug was that a well documented function actually behaved differently than was expected but still consistently (like a string function that was supposed to return a number of characters but really returned a number of bytes) then yeah, that's a breaking change.
In practice the line can be fuzzy of course, but I find that it's not usually to hard to decide what constitutes a breaking change and what doesn't.
Apart from the ABI thing, which is pretty clear-cut - most bug files should not break the public Api - but sometimes the api spec is buggy. Then bug fix becomes a breaking change.
Assume that ssl certs are never actually checked[1] - this is typically a bug - and a bad situation. I would probably assume fixing such a bug would be a breaking change, even though it's a case of "omg, hair on fire this never was working" - and clearly a bug...
[1] yeah that's a real example https://www.python.org/dev/peps/pep-0476/
If you can re-link with the new library but something no longer works, you need to emit lots of very loud warnings when code calls that function.
Seems like Major increment to me. But! If the fix is breaking some previous undefined behaviour to work correct then I think Minor with relnote. But! If the code is not in wide use, bump Patch and move on.