I'm a recent convert to Remember the Milk[0], can't recommend it enough (the apparent stable business model is a plus as well, I recall using them back in the Blackberry era)
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.
The same reasons [0] are why I have a Chromebook. CrOS is limited, sure, but the limits make the thing bloody near invincible (and amazingly productive).
[0] Hangouts are luckily the VoIP of choice for most I work with
APK size takes a small hit, and there's extra work to bring in Java libraries. That's all I've found. I've actually been using their guides when working on ordinary Java-based Android code; their docs are well-written and their SDK maps nearly 1:1 to Google's (helps here that Java and C# are fairly similar to a degree).
[0] http://rememberthemilk.com