Not knowing Prolog (or any other "4th gen declarative langauge", besides from SQL), I don't know if it's any different but my main peeve with anything fully declarative is that it can be deceiving. One expression computes fine and then you change it in a seemingly insignificant way and suddenly it's three orders of magnitude slower, because underneath the surface, it still translates into loops and jumps, only now you don't know which ones.
Prolog's execution model is well defined so there shouldn't be any surprises to the proficient programmer. I'd argue it's less surprising than what a C optimizing compiler does.
There is a certain clarity of purpose declarative code has that I find really pleasing.
Also I'm lazy and I prefer if the computer thinks for me.