The major obstacle in coming to terms with relativity theory is the objection from our own intuition. In addition to that, the formulas of special relativity are apparently more complicated than those of classical mechanics. This all happens because we seek an understanding of new phenomena in terms of such mathematical and physical concepts, and even senses, that developed for a very long time against a fundamentally different backdrop.
It does not help either that special relativity discovers more the "what" than the "why". As a logical process, it derives the strange consequences of a counter-intuitive assumption about light. It would be better for understanding if one could derive the same consequences from a more intuitive assumption instead. (It's not as hopeless as it sounds, take for example the many surprising consequences of the non-surprising law of conservation of angular momentum.)
In the future, when relativistic effects become more and more a common experience, the concepts and formulations of the theory, as well as our intuition, will adapt and hopefully make relativity look simpler and more intuitive to grasp. Nevertheless, as suggested by von Neumann, we never really understand a theory. It can only become intuitive at best, once we've managed to get used to it.