Works for me - I have a StartSSL personal cert and an Android phone (Nexus 5 / KitKat), and all of Chrome, Chrome Beta, and Firefox load up the site without any sort of warning or other indication. I also dug out a Jelly Bean phone (Galaxy Nexus) to try with the stock Android Browser and didn't have any issues.

I haven't checked any recent Android trust stores, but this might be due to a lack of an intermediate certificate.

The vast majority of modern browsers know how to find intermediate certificates online. Android's browser doesn't, for whatever reason. You have to bundle it on your web server.

StartSSL has worked on Android since version 2.2, which was released 4 years ago.