I think the problem is that OOP is mostly taught as a separate paradigm, when it should be seen as a convenience layer over procedural imperative programming. It is about bundling procedures together in groups, associating them with mutable state, and protecting and encapsulating that state from other pieces of code.
Yes, I agree, my experience is also that OOP is taught as something orthogonal over procedural imperative programming whereas it should be taught as an extension to it. But even with that said I honestly cannot think of many examples where OOP provides more elegant solution to the problem. Quite the contrary, any larger and more complex OOP-style codebase is quite an unreadable mess despite all the standard promises about the readability, maintainability, "testability", clean abstractions etc.
I think that the biggest bend in my mind was when I set myself a goal to try to digest "Elements of Programming" by A. Stepanov and "Modern C++ Design" by A. Alexandrescu. Don't let the "modern" in the title trick you, it's a book from 2001.
But irrelevant of the programming language, which in my example happens to be the C++, these two books triggered me to start challenging the tunnel vision I had up until then. It took me some time and a lot of experimentation to basically unlearn the OOP way of approaching the problems and trying to embrace a totally different, I'd say, almost mathematical way of looking at the things. It felt like a relief and it really had a huge impact not only on my code style but the way I think about the problems.
Since then I think I started producing much simpler and, what I think, non over-engineered code of better quality without a lot of unnecessary cruft.
The bigger problem is that OOP isn't even consistently defined. Kay's (who is oft credited with inventing the term) definition revolves around message passing, which negates the idea of it being a layer over procedural imperative languages as Erlang fits his model of OOP.
