Why is automatically labeling data in unsupervised learning hard?
The problem with your intuition is that, frankly, you don't have one. At least not a useful, that is algorithmic one, one that tells you what is hard for computers and what is not. You think in terms of what you can do with every-day data -- but that's not an appropriate frame of reference for this problem. As evidence, consider this question.

Some specific concerns:


"I can" != "I can build an algorithm which can". 
Can you? Look at some data dumps from CERN and try to classify them. 
What exactly are "features" (mathematically)?
What does "fits best" mean (mathematically)?


I recommend three things that will help you build a (better) intuition.


Study computability and complexity theory -- this will help you build intution for hardness of computational problems.
Program things -- this will help you build intution for hardness of implementing things.
Try to build an unsupervised learner and fall into all the pitfalls.