Barrapunto

Por lo menos, StartSSL no es una CA preinstalada, como indican en su FAQ:

Why does Firefox present a warning when connecting to my website?

If you receive a warning that the certificate is signed by an "untrusted authority", than the installation of the server certificate isn't complete. You must add the intermediate CA certificate to your installation.
--
"En teoría no hay diferencia entre teoría y práctica. En la práctica, sí la hay."

Realmente a lo que se está refiriendo es que a la hora de configurar el certificado en el servidor es que se ha configurado de forma incorrecta y la cadena de certificados del lado del servidor no está completa. Hace falta meter el CA y luego el intermediate. En el caso del gratuito es el intermediate Class 1. En la jerarquía de certificados por tanto estaría el CA raíz del cual dependen los intermedios, entonces el CA intermedio class 1 que en nuestro caso es el que certifica los gratuitos y nuestro certificado propio también tiene que estar en el servidor. Esto es para poder hacer la validación correctamente, por tanto sí es preinstalado, por ello está en la lista de certificados raíz del sistema como confiable. Observa:

Este es el CA raíz:
http://www.startssl.com/certs/ca.crt [startssl.com]

Este es el CA intermedio para los gratuitos (class 1):
http://www.startssl.com/certs/sub.class1.server.ca .crt [startssl.com]

Para que funcione hay que tener la cadena completa en el servidor: raíz (CA), intermediario y luego el certificado emitido para el dominio.

En ese FAQ sencillamente indican que muchas veces no completan el bundle y cometen el error habitual de instalar solo el raíz.