There are several difficulties with pointers:
- Aliasing The possibility of changing the value of an object using different names/variables.
- Non-locality The possibility of changing an objects value in a context different from the one in which it is declared (this also happens with arguments passed by reference).
- Lifetime Mismatch The lifetime of a pointer may be different from the lifetime of the object it points to, and that may lead to invalid references (SEGFAULTS) or garbage.
- Pointer Arithmetic. Some programming languages allow the manipulation of pointers as integers, and that means that pointers can point anywhere (including the most unexpected places when a bug is present). To use pointer arithmetic correctly, a programmer must be aware of the memory sizes of the objects pointed to, and that's something more to think about.
- Type Casts The ability to cast a pointer from one type to another allows overwriting of the memory of an object different from the one intended.
That's why a programmer must think more thoroughly when using pointers (I don't know about the two levels of abstraction). This is an example of the typical mistakes made made by a novice:
Pair* make_pair(int a, int b)
p.a = a;
p.b = b;
Note that code like the above is perfectly reasonable in languages that don't have a concept of pointers but rather one of names (references), objects, and values, as functional programming languages, and languages with garbage collection (Java, Python) do.
The difficulty with recursive functions happens when people without enough mathematical background (where recursiveness is common and required knowledge) try to approach them thinking that the function will behave differently depending on how many times it has been called before. That problem is aggravated because recursive functions can indeed be created in ways in which you do have to think that way to understand them.
Think of recursive functions with pointers being passed around, like in a procedural implementation of a Red-Black Tree in which the data structure is modified in-place; it is something more difficult to think about than a functional counterpart.
It's not mentioned in the question, but the other important issue with which novices have difficulty is concurrency.
As others have mentioned, there is an additional, non-conceptual problem with some programming language constructs: it is that even if we understand, simple and honest mistakes with those constructs can be extremely difficult to debug.