It seems that this is independent of where I run the project. It happens with default project, which has no ":eval-in :trampoline" in it:
$ lein new my-project
$ cat my-project/project.clj
(defproject my-project "0.1.0-SNAPSHOT"
:description "FIXME: write description"
:url "http://example.com/FIXME"
:license {:name "Eclipse Public License"
:url "http://www.eclipse.org/legal/epl-v10.html"}
:dependencies [[org.clojure/clojure "1.5.1"]])
$ cd my-project/
$ lein repl
REPL server launch timed out.
And it also happens if I run lein repl outside of any project.
I have already used repl on this machine in the past and I noticed the problem when I tried to use cider. I just assumed that the problem was in emacs packages (I think I tried cider instead of nrepl at the time) but didn't have time to check. Now I see that I can't even run repl with leiningen.
I suspect some update of some package (jdk maybe?). I didn't find anything in apt-get and dpkg logs, but they might not cover long enough time range. The problem is that I don't know when did this start, as I almost didn't use clojure in the last two months.