I think a lot of the difficulty in Prolog comes down to the fact that you can read Prolog programs three ways: as a restricted form of first order logic (Horn clauses), as a procedure, and as an execution model. The last is double confusing because almost all programmers are used to controlling the execution model and Prolog demands that you relinquish a lot of control there ("Algorithm = logic + control" by Kowalski talks about this a bit). You also cannot ignore any of them because any non-trivial Prolog program exploits all three.