It's easier to get Lein as standalone. The Ubuntu package depends on half the build infrastructure of java, using really minimal parts of it here and there. If you just get the shell script and stuff it in your path, it can self-install a 10MB jar that has all it needs.
Wait, are you trying to install it as an APT package? It's probably easier to just download the script and install it that way. If you do that, it will install all the libraries to a folder in your home directory.
Wow, that's a pretty skimpy list of dependencies. But..
"Make sure you're using Leiningen 2."
..argh, installing that on ubuntu that requires 110 packages. All that just for a build system?