CL's iteration primitives are more capable that those provided by most languages, which often makes for a very clean approach.
Recursion is sometimes the easiest way to reason about a problem though, so it's nice to have decent support and TCO.
> Recursion is sometimes the easiest way to reason about a problem though
Yes, it's one of the things that allow FP algorithms to be more declarative. It's difficult to seriously argue that recursion is fundamentally more complex-- the contrary argument is more obvious to me.
Everything that's left is the fact that it requires people to unlearn things, which is uncomfortable and requires effort, but unfamiliarity is not an indicator of complexity.
Scheme likes to tout it because of tail call optimization. Common Lisp can do it, but doesn't really shove it as a first principle of "Common Lisping" (and CL does not dictate tail call optimization).
I don't use it (save when it's necessary). I just iterate using the supplied iterators (do, dolist, loop, whatever).
I can't speak to other functional languages.