I'm led to believe the issues with Clojure (and other JVM languages) on Android are due to Dalvik not being as friendly to other languages as the Sun JVM. I don't blame Google, but it's unfortunate.
There are actually games written in Clojure that run on Android quite well. A bit slow to start up, but not nearly as bad as I had expected. Take a look at https://play.google.com/store/apps/details?id=com.friendlyvi... and check out their development blog.
EDIT: The guy who did NightWeb talks about Clojure on Android here: http://nightweb.net/blog/clojure-on-android.html