Creating a new CA certificate and signing all your services’ certificates with it is obviously not enough, you also need to install your new root CA to all your devices.

Debian

Add the root CA to /usr/local/share/ca-certificates, then run update-ca-certificates (which builds a database that is used by cadaver, wget and others).

Android

In Parameters, Security, below Trust certificates there is an Install from SD card entry. Select the CRT file, give it a name. It’s not clea whether the “Certificate use” actually is used: adding my root CA ås “VPN and applications” lets the Android mail application connect to my IMAP server.

Firefox / Thunderbird

These have their own trust store each, which means you need to install it twice. In both cases, Preferences, Advanced, Certificates, View Certificates, Authorities, Import. So simple.