OOP is unnatural for some problems. So's procedural. So's functional. I think OOP has two problems that really make it seem hard.
Some people act like it's the One True Way to program and all other paradigms are wrong. IMHO everyone should use a multiparadigm language and chose the best paradigm for the subproblem they're currently working on. Some parts of your code will have an OO style. Some will be functional. Some will have a straight procedural style. With experience it becomes obvious what paradigm is best for what:
a. OO is generally best for when you have behaviors that are strongly coupled to the state they operate on, and the exact nature of the state is an implementation detail, but the existence of it cannot easily be abstracted away. Example: Collections classes.
b. Procedural is best for when you have a bunch of behaviors that are not strongly coupled to any particular data. For example, maybe they operate on primitive data types. It's easiest to think of the behavior and the data as separate entities here. Example: Numerics code.
c. Functional is best when you have something that's fairly easy to write declaratively such that the existence of any state at all is an implementation detail that can be easily abstracted away. Example: Map/Reduce parallelism.
OOP generally shows its usefulness on large projects where having well-encapsulated pieces of code is really necessary. This doesn't happen too much in beginner projects.