I don't know if they teach this anymore, but when I was in CS 20 years ago we learned about a method of programming called "abstract data typing." The idea was you have some data structures, each of which can be instantiated multiple times, and you have sets of procedures that work on those data structures, with each set of procedures assigned to each data structure type. We used to use this concept in C to make complex systems a little more manageable.
Modern "OOP" languages accomplish this by having the programmer set up classes with member variables (the data structures), and associated procedures. Each procedure has an implicit "this" pointer/reference, so that when it's called, the object that references the procedure (I'm talking syntactically, not how it actually happens) is passed into the procedure automatically, so that it can access the structure's variables without the programmer passing in the structure explicitly every time. In addition, there are compiler checks to make sure the type tags match up (a method of making sure you don't call the wrong procedure for a data structure), and that access constraints are enforced on both structure variables, and procedures. The language makes it look like everything is one happy unit, but it's really not. It's an abstraction on top of the ADT concept. The problem with this scheme is while this helps manage complexity some (which is more attributable to an extra layer of scoping than anything else), you're not dealing with "objects" in the best sense of the concept.
In one better conception, the procedures are somehow directly linked with the information they manipulate. In other words, there's no need to have a type bind them together, because they are bound together implicitly. Secondly, procedures represent a "protocol" for the object, and anything that can work with that protocol can work with it. In effect the object's protocol (interface) is its type! This allows more flexibility in object relationships, because any method that can work with a protocol with one object can work with any other object that conforms to the same protocol. Translating this into "type" parlance, this means that any object can span multiple "types" just by conforming to multiple protocols.
By adhering to this "protocol" concept, you isolate different implementations, because all a method ever cares about is the behavior of the protocol of another object.
What I've seen with modern "OOP" languages is programmers have to add in a LOT of cruft just to get to something that approaches this concept, creating abstract interfaces, which allow looser binding to object types. The problem with this scheme is it assumes that type tags can substitute for the notion of a protocol-type. They can't, really.
Secondly, the static typing we have in our languages tends to get in the way. This is the reason "OO" languages developed templates and generics, and later a "dynamic" type. They're all "escape hatches" from static typing. The reason they were developed is people want to express a concept more generally, while keeping the expression succinct. It seems to me it would be better to make type constraints optional, something that can be added in at will, once a design has been tested and accepted.
Further, most programmers I've seen don't even bother with objects that much. They use the APIs that come with the language, using some notion of objects, but they just write straight procedures for their own code, practically eschewing any notion of objects, except where they're convenient.
A point that was made earlier about programmers making patterns into a religion, rather than an interesting engineering approach to a problem, is a good one, though I wouldn't attribute this just to OOP. It's really an issue that technologists get fascinated with technology. Secondly, a lot of us dislike change. This gets expressed as a desire to make a system "fit" a standard design language (a set of canonical patterns). You see this in programming language choices, too, which is another version of the same thing. This way, programmers versed in the patterns can refer to "this is a 'that' pattern," and such, and everyone can nod and know what you're talking about. No one has to explain what's really going on, because just by referring to labels, everyone gets the idea quickly. The problem is our design language is not complete. So instead we make do with an incomplete language, because "everybody knows it."
It's not that OO is too complicated. I think OO is good for some situations, but not all. The real problem is that our notions of OO, and our tools for accessing that concept, not to mention our notions of design, are really poor.
Keep Up with TechRepublic