(I was thinking of tattoos, PS.)
With TCO, you can use a set of mutually-recursive functions - you can set up a FSM via tail calls, use CPS for backtracking (and many other things), a re-entrant virtual machine where each opcode is a tail call (rather than a giant switch/case or lots of gotos), etc. Being able to use function calls like "gotos with arguments" (but with local scopes, etc.) can make some constructs much easier to read, reason about, etc.
I'm not that familiar with the implementation of the JVM, but AFAICT it's due to difficulties setting up tail calls efficiently in JVM bytecode.
As soon as the JVM supports it Clojure will support it. For me recur and trampoline are quite ok. I would want to miss on clojure because of TCO but I don't know what would be possible with TCO. I hope I can learn that in one of the books I have here :)
And yeah, I thought of mentioning trampolines, didn't know that it already had a readymade one. Sometimes they add too much overhead, but often it's still a good trade-off.