Something the other answers haven't mentioned: state.
You talk about OO as a tool for managing complexity. What's complexity? That's a fuzzy term. We all have this geshtaltgestalt sense of what it means, but itsit's harder to pin it down. We could measure cyclomatic complexity, i.e. the number of run-time paths through the code, but I don't know that's what we're talking about when we use OO to manage complexity.
What I think we're talking about is state-related complexity.
There are two main ideas behind encapsulation. One of them, the hiding of implementation details, is pretty well-covered in the other answers. But another is hiding its run-time state. We don't muck around with objects' internal data,data; we pass messages (or call methods if you prefer implementation detail over concept as Jörg Mittag pointed out). Why?
People have already mentioned itsit's because you can't change the internal structure your data without changing the code the accesses it, and you want to do that in one place (the accessor method) instead of 300 places.
But itsit's also because it makes the code hard to reason about: procedural code (whether in a language that is procedural in nature or is simplesimply written in that style) offers little help for imposing restrictions on the mutation of state. Anything can change at anytime from anywhere. Calling functions/methods may have spooky action-at-a-distance. Automated testing is more difficult, since the success of the tests is determined by the value of non-local variables that are widely accessed/accessible.
The other two large programming paradigms (OO and Functionalfunctional) offer interesting, but almost diametrically opposed solutions to the problem of state related complexity. In Functional Programmingfunctional programming one tries to avoid it entirely: functions are generally pure, operations on data structures return copies rather than updating the original in place, etc.
OO on the other hand offers tools to deal with managing state (instead of tools for avoiding it). In addition to the language-level tools like access modifiers (protected/public/private), getters and setters, etc. there are also a number of related conventions like the Law of Demeter which advises against reaching through objects to get at other objects data.
Note that you don't need objects to do really any of this: you could have a closure that has inaccessible data and returns a data structure of functions to manipulate it. But isn't that an object? Doesn't that fit our conception of what an object is, intuitively? And if we have this concept, isn't it better to re-ify it in the language rather than (as other answers have said) relying on a combinatorial explosion of competing ad-hoc implementations?