Do Java programmers find mutable variables in general horrifying? That was not my impression - certainly, the language doesn't make it easy to make everything immutable. If so, why the special distinction for lambdas?

The official rationale was that they expected lambdas to be mostly used for parallel sequence processing, and wanted to avoid race conditions. Of course, in practice, lambdas are very useful in many other places, where there's no concurrency issue at all - async continuation callbacks, for example, or pseudo-custom language constructs implemented as functions with a lambda for a body.