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.