insight why this seems to be so difficult?
I have studied CS with a side-dish of math (some decades ago) and I was surprised by (but very much enjoyed) the actual theoretical aspects of CS. I generally didn't know what to expect from a CS curriculum except that in my case it was abundantly clear that I wanted to study whatever there is to know about computers etc.
Therein might lie your problem. Many of your students probably had no idea what CS entails, didn't expect it so heavily related to maths (i.e., logic, proofs, formulae etc.) and are quite unable to cope with languages, grammars, automata, lambda calculus, O-notation and so on. Also I'd suggest that a healthy percentage couldn't care less and have zero intrinsic interest. At least that was the case in the cohort I studied back then.
In my case, at least 50% of all students bowed out within the first 4 semesters, and without having any statistics, I assume that was because of maths and theoretical CS, mostly.
Another point is this: since the beginning of my time in the workforce, first as programmer and then as still-programming/developing/architecting/coaching teamlead, I over and over find that young programmers (who, in my company, usually have studied CS or something very close at uni levels) love to solve problems by cut&paste; by going to Stack Overflow; by reading tutorials and so on. Having worked closely with dozens if not more people over the decades, I think I met exactly one person who (like me) actually went to the reference documention of whatever tool or programming language we used, first, when trying to understand it or solve a deep problem. Almost everybody else seems to have a deep aversion against really "grokking" some topic from first principles.
Sure, just going to a tutorial and copying some lines of code is usually quicker, and often the software kind of works at the end; but for me personally, I get my satisfaction from deeply understanding what I am doing; I am fascinated by digging deep. Meanwhile, I am very aware that this is not normal for everybody, even CS students. This is a bit of a parallel to your definitions - the core documentation of whatever you're using is the definition, and a tutorial would be something like a practical example.
As to "why" that is, I assume that CS (especially theoretical, but basically all of it) is by its very nature not "natural" for humans to learn and do. This is probably also the reason why we have such a shortage, worldwide, of people really excelling at it. If it were easy and came to most of us as a matter of course, we would have boatloads of people easily chugging out software and advancing the field...
Are there any better techniques to get this point across?
Unfortunately I find it very hard to suggest anything except repeating your point over and over again. At least in my country, alas, due to changes to the school system in the last decade (EU -> Pisa...) I am afraid that schools do not have the time or capacity anymore to really bring the pupils to uni-level logical thinking, primarily cramming facts and forgetting them as quick as possible to make space for the next test. This is only partially cynical - that opinion comes from talking with and experiencing the education of some of them, including one of my adult children.
Maybe in your next class, take out the first 2-3 sessions to talk about nothing else except how to approach these things (basically, what you explained in your post). Make them aware what they have to expect, and give them techniques to actually do the work. Maybe, in the first time, after actually teaching your first few definitions, take another hour or two just for Q&A where you test them on it and make it routine for them to go to the definitions.
Maybe, on your test sheets, write a message "go back to your definitions whenever you don't know what to do" in big letters.