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 geshtalt sense of what it means, but its 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, we pass messages (or call methods if you prefer implementation detail over concept as Jörg Mittag pointed out). Why?

People have already mentioned its 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 its also because it makes the code *hard to reason about*: procedural code (whether in a language that is procedural in nature or is simple 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 Functional) offer interesting but almost diametrically opposed solutions to the problem of state related complexity. In Functional 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?